정올 1828 : 냉장고

Java

1828 : 냉장고

문제

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

접근 방법

문제를 이해하기 조금 힘들었는데, 해석하면
특정 온도로 유지되고 있는 냉장고 k개가 있다.
이 냉장고의 유지하고 있는 온도에 들어갈 수 있는 화학 물질들을 넣을 수 있고, 이 냉장고 k개의 최소를 구하는 것이다.
즉, 각 화학물질들의 최소 온도와 최대 온도 사이 온도들이 최대한 겹치게 냉장고 온도를 설정하여 k개를 놔두면 된다.

주어진 예제를 1차원 그래프로 나타내어 보았다.
빗금친 [-10 ~ 5]와 [27 ~ 44] 사이에 각각 냉장고의 온도를 설정하면, 해당하는 냉장고에 화학 물질을 2개씩 배정 할 수 있다.

구현

최고 온도를 기준으로 오름차순으로 화학 물질을 재 정렬한다.
이후 각 화학 물질의 최저 온도가 이전 화학 물질의 최고 온도보다 낮으면, 서로 온도가 겹치므로 하나의 냉장고에 보관할 수 있다.
따라서 이전 물질의 최고 온도보다 현재 물질의 최저온도가 더 높으면, 냉장고를 하나 더 추가하고 현재의 최고 온도를 기준 최고온도로 재설정한다.
이후 전부 탐색 하여 냉장고의 수를 구한다.

코드

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

public class Main {
	
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk; 
    	int n = stoi(br.readLine());
    	Pair[] ci = new Pair[n]; 
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		ci[i] = new Pair(stoi(stk.nextToken()), stoi(stk.nextToken()));
    	}
    	
    	int result = 1;
		// 최고 온도 기준으로 오름 차순으로 정렬한다.
    	Arrays.sort(ci, new Comparator<Pair>() {
			@Override
			public int compare(Pair o1, Pair o2) {
				return Integer.compare(o1.b, o2.b);
			}
		});
    	
		// 최고 온도가 제일 작은 것을 기준으로 한다.  
    	int r = ci[0].b;
    	
    	for(int i = 1; i < n; i++) {
    		if(r < ci[i].a) {	// 현재 물질의 최저 온도가 기준 최고온도보다 더 크면, 냉장고를 추가하며 기준을 변경한다. 
    			r = ci[i].b;
    			result++;
    		}
    	}
    	
    	System.out.println(result);

    	
    	br.close();
    }
    
    static class Pair {
    	int a,b;
    	Pair(int a, int b){
    		this.a = a;
    		this.b = b;
    	}
		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("Pair [a=").append(a).append(", b=").append(b).append("]");
			return builder.toString();
		}
    	
    }
    
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

★★★★★

후기

개선할 점

최고온도 기준으로 정렬해야할 이유를 아직 확실히 파악하지 못하였다.