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

문제

JUNGOL

풀이

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N;
	static int RefreNum;
	private static class Temperatures implements Comparable<Temperatures> {
		int min;
		int max;
		
		public Temperatures(int min, int max) {
			this.min = min;
			this.max = max;
		}

		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("Temperatures [min=");
			builder.append(min);
			builder.append(", max=");
			builder.append(max);
			builder.append("]");
			return builder.toString();
		}

		@Override
		public int compareTo(Temperatures o) {
			int diff = this.max - o.max;
			return diff != 0 ? diff : this.min- o.min;
		}
	}
	
	public static void main(String[] args) throws Exception {
		N = stoi(br.readLine());
		Temperatures[] temps = new Temperatures[N];
		RefreNum = N;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			temps[i] = new Temperatures(stoi(st.nextToken()), stoi(st.nextToken()));
		}
		Arrays.sort(temps);
		int maxNum = temps[0].max;
		for(int i=0 ; i < N-1 ; i++) {
			if(maxNum >= temps[i+1].min) {
				RefreNum--;
			} else {
				maxNum = temps[i+1].max;
			}
		}
		
		System.out.println(RefreNum+"");
	}
	
	static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

 

최대 냉장고 개수(RefreNum)는 N이므로 N으로 초기화한다. 

4
-15 5
-10 36
10 73
27 44

입력 예가 위와 같을 때, 4개의 화학물질 C에 해당하는 최저온도와 최고온도를 아래와 같은 표로 나타낼 수 있다.

파란 숫자는 최저 온도를, 빨간 숫자는 최고 온도를 나타낸다. 

나는 이때, 최저 온도를 기준으로 정렬하면 더욱 쉽게 냉장고 개수를 줄일 수 있을 것이라고 판단했다.

이때, Comparable을 implements 하여 compareTo를 오버라이딩해 사용했다.

		@Override
		public int compareTo(Temperatures o) {
			int diff = this.max - o.max;
			return diff != 0 ? diff : this.min- o.min;
		}

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

그 후, Arrays.sort() (==> 오버라이드한 compareTo 함수를 이용해 정렬해줌) 를 통해 아래와 같이 정렬했다.

---

1. 첫번째 화학물질의 최고온도(max)를 maxNum으로 둔다.

2. 두번째 화학물질의 최저 온도(min)가 더 낮다면 같은 냉장고를 사용할 수 있으므로 냉장고 개수를 줄인다.

3. 세번째 화학물질의 경우엔 maxNum 보다 temps[i+1].min(세번째 화학물질의 최저 온도)이 더 높다. 이런 경우엔 같은 냉장고를 사용할 수 없음을 의미한다.

이땐, maxNum을 세번째 화학물질의 최고온도로 바꿔주기만 한다. 

4. 이제 네번째 화학물질의 최저 온도가 세번째 화학물질의 최고 온도(maxNum) 보다 낮다면 같은 냉장고를 쓸 수 있다는 것을 의미하므로 냉장고 개수를 하나 줄인다.

( 처음에 최저 온도를 기준으로 정렬했기 때문에 네번째 화학물질의 최저 온도가 세번째 화학물질의 최저 온도보다 낮은 경우는 고려하지 않는다.)

답(RefreNum)은 2가 된다.

 

그리디 알고리즘을 풀때 순서를 바꿔도 상관이 없다면 정렬하는 것이 큰 도움이 될 때가 있다. 이와 비슷한 문제로는 백준 회의실 배정 문제가 있다.

www.acmicpc.net/problem/1931

1931번: 회의실 배정