[정올] 1828번: 냉장고 (Java) / 그리디

<정올 1828번. 냉장고>

- Greedy 그리디 문제

문제

N개의 화학 물질 C1, C2, …, Cn이 있다. 

이들 각각은 보관되어야 할 온도가 각기 다른데, 각 Ci마다 최저 보관 온도 xi와 최고 보관 온도 yi가 정해져 있다. 

즉 Ci는 온도 xi이상, yi이하의 온도에서 보관되어야만 안전하다.

 

이 화학 물질들을 모두 보관하기 위해서는 여러 대의 냉장고가 필요한데 가능하면 적은 수의 냉장고를 사용하고 싶다. 

이를 해결하는 프로그램을 작성하시오.

 

입력형식

첫줄에 화학물질의 수 N이 입력된다. N의 범위는 1이상 100 이하이다. 

두 번째 줄부터 N+1줄까지 최저보관온도와 최고보관온도가 입력된다. 

보관온도는 -270° ~ 10000°이며, 각 냉장고는 임의의 정해진 온도를 일정하게 유지할 수 있고, 냉장고는 아주 크다고 가정한다.

 

출력형식

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

 

 

소스코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main_1828_냉장고 {
	
	static class Temp implements Comparable<Temp>{		// 화학물질은 온도 정보
		public int lowest;	// 최저 보관 온도
		public int highest;	// 최고 보관 온도
		
		public Temp(int lowest, int hightet) {
			super();
			this.lowest = lowest;
			this.highest = hightet;
		}

		@Override
		public int compareTo(Temp o) {	//먼저 최고 기온을 기준으로 정렬(오름차순) 한 후, 만약 최고 기온이 같다면 최저 기온을 기준으로 정렬(오름차순) 한다.
			int diff = this.highest - o.highest;
			return diff != 0 ? diff : this.lowest-o.lowest;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();	// 화학물질의 수
		int count = 0;		// 냉장고 개수
		int curLow = 0;		// 현재 냉장고의 최저온도
		int curHigh = 0;	// 현재 냉장고의 최고온도
		
		Temp[] temps = new Temp[N];
		
		for(int i=0; i<N; i++) {
			temps[i] = new Temp(sc.nextInt(), sc.nextInt());	// 데이터 입력
		}
		
		/*// 최고보관온도를 기준으로 오름차순 정렬
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				if(temps[i].highest > temps[j].highest) {
					Temp temp = temps[i];
					temps[i] = temps[j];
					temps[j] = temp;
				}
			}
		}*/
		
		Arrays.sort(temps);    // 최고 온도를 기준으로 오름차순 정렬
		
		// 첫번쨰 냉장고의 온도를 첫번쨰 화학물질의 온도로 셋팅
		curLow = temps[0].lowest;
		curHigh = temps[0].highest;
		count++;
		
		for(int i=1; i<N; i++) {
			if( temps[i].lowest > curHigh ) {	// 현재 냉장고의 최고 온도보다 높은 최저온도의 재료를 만나면
				curLow = temps[i].lowest;		// 그 재료의 최저온도로 냉장고를 셋팅
				curHigh = temps[i].highest;		// 그 재료의 최고온도로 냉장고를 셋팅
				count++;	// 냉장고 추가
			}
		}
		System.out.println(count);
	}
}

 

 

풀이

1. 최고 온도를 기준으로 오름차순으로 정렬

 

 ==> Temp class를 작성했기 때문에,

Comparable을 implements하여 compareTo를 오버라이딩하여 사용.

@Override
public int compareTo(Temp o) {	//먼저 최고 기온을 기준으로 정렬(오름차순) 한 후, 만약 최고 기온이 같다면 최저 기온을 기준으로 정렬(오름차순) 한다.
    int diff = this.highest - o.highest;
    return diff != 0 ? diff : this.lowest-o.lowest;
}

먼저 최고 기온을 기준으로 정렬(오름차순) 한 후, 만약 최고 기온이 같다면 최저 기온을 기준으로 정렬(오름차순) 한다.

 

 

2. 첫번째 화학물질의 최고온도를 curHigh, 최저온도를 curLow로 둔다.

 

 

3. 두번째 화학물질의 최저온도 (temps[i].lowest) 가 curHigh 보다 더 낮다면 같은 냉장고 사용,

최저온도 (temps[i].lowest) 가 curHigh 보다 더 높다면 같은 냉장고를 사용할 수 없음을 의미한다.

 

 ==> 이때에는 curHigh를 두번째 화학물질의 최고 온도로 바꿔주고,

         냉장고 개수를 하나 증가시킨다.