[JUNGOL/JAVA] 정올 1828 : 냉장고 (자바)

문제 정보

Intermediate_Coder
  문제명   - 냉장고
문제 번호 - 1828번

---

문제 링크

Jungol_1828_냉장고 

JUNGOL

---

문제

N개의 화학 물질 C1, C2, …, Cn이 있다. 
이들 각각은 보관되어야 할 온도가 각기 다른데, 각 Ci마다 최저 보관 온도 xi와 최고 보관 온도 yi가 정해져 있다. 
즉 Ci는 온도 xi이상, yi이하의 온도에서 보관되어야만 안전하다.
 
이 화학 물질들을 모두 보관하기 위해서는 여러 대의 냉장고가 필요한데 가능하면 적은 수의 냉장고를 사용하고 싶다. 
이를 해결하는 프로그램을 작성하시오.

---

입력

첫줄에 화학물질의 수 N이 입력된다. N의 범위는 1이상 100 이하이다. 
두 번째 줄부터 N+1줄까지 최저보관온도와 최고보관온도가 입력된다. 
보관온도는 -270° ~ 10000°이며, 각 냉장고는 임의의 정해진 온도를 일정하게 유지할 수 있고, 냉장고는 아주 크다고 가정한다.

---

출력

첫줄에 최소로 필요한 냉장고의 대수를 출력한다.

---

예제 입력/출력

예제 입력	예제 출력
4 -15 5 -10 36 10 73 27 44	2

---

알고리즘 분류

● 그리디

---

소스코드

package Intermediate_Coder_03_탐욕알고리즘;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 그리디
 * http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=3050
 */
public class Jungol_1828_냉장고 {
	static class Temperature implements Comparable<Temperature>{
		int row, high;
		
		public Temperature(int row, int high) {
			this.row = row;
			this.high = high;
		}
		@Override
		public int compareTo(Temperature o) {
			// 최고보관온도 오름차순 정렬, 최고보관온도가 같다면 최저온도 오름차순 정렬 
			return this.high != o.high?this.high-o.high:this.row-o.row;
		}
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		// N : 화학 물질의 수
		int N = Integer.parseInt(br.readLine());
		Temperature[] temper = new Temperature[N]; 
		// 최저보관온도, 최고보관온도 값 입력
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			temper[i] = new Temperature(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		// 최고보관온도 오름차순 정렬
		Arrays.sort(temper);
		// 첫번쨰 냉장고를 첫번째 재료의 최대온도로 설정
		int count = 1;
		int max = temper[0].high;
		
		// 두번쨰 재료부터 검사
		for (int i = 1; i < N; i++) {
			// 냉장고의 온도보다 높은 최저보관온도를 가진 재료를 만나면
			if(max < temper[i].row) {
				// 다음냉장고 온도를 그 재료의 최고보관온도로 설정
				max = temper[i].high;
				count++;
			}
		}
		System.out.println(count);
		br.close();
	}
}

---

JungOl List

JungOl List

---

  

기회는 준비된 자에게 찾아온다.

 

---