[Jungol][Java][Greedy,활동 선택 ] 1828 - 냉장고

jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=30

JUNGOL

문제

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

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

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

 

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

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

 

입력형식

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

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

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

 

---

문제 풀이

 

해당 문제는 활동 선택의 전형적인 문제이다.

 

활동 선택 문제는 회의실 시간을 최대로 배정하는 방법과 같은 문제를 말한다.

 

예를 들어, 지정된 시간동안 회의실을 최대한 많이 배정하기 위해서는 회의실이 끝나는 시간으로 내림차순 정렬한 후에 현재 회의실 끝나는 시간보다 시작하는 시간이 더 늦다면 회의실을 새로 업데이트 하는 방식을 말한다. (이때, 끝나는 시간이 동일할 경우 시작하는 시간순으로 정렬한다.)

 

 

이와 같은 방식으로 해당 문제에서는 냉장고의 '최고 보관 온도'를 기준으로 내림차순 정렬한다. (최고 보관 온도가 동일할 경우 최저 보관 온도가 낮은 순으로 재정렬)

 

그 후 최고 보관 온도보다 높은 낮은 보관온도를 가진 물질이 있다면 냉장고의 범위가 겹치지 않기에 필요한 냉장고의 수를 + 1 을 해준다. 그 후 해당 물질의 최고 보관 온도로 현재 냉장고의 보관 온도를 새로 update 해준다. 

 

단, 우선순위가 제일 높은 첫 물질은 반드시 냉장고에 들어가야 함으로 초기에 저장해준다.

 

코드로 보면 다음과 같다.

 

package jungol;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

// 냉장고 , greedy.
// 최고온도로 정렬(같으면 최저 온도가 낮은순으로) 
public class Main_1828 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =null;
		int N=Integer.parseInt(br.readLine());
		Chemical[] c = new Chemical[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			c[i]= new Chemical(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		Arrays.sort(c);
		
		// 첫 물질은 반드시 냉장고에 보관된다.
		int cnt=1;
		int endT=c[0].h;
		for(int i=1;i<N;i++) {
			// 기존 끝 온도보다 더 높은 온도가 있다면 끝온도 update.
			if(endT < c[i].l ) {
				endT=c[i].h;
				cnt++;
			}
		}
		
		System.out.println(cnt);
		

	}

}

class Chemical implements Comparable<Chemical>{
	int l,h;

	public Chemical(int l, int h) {
		super();
		this.l = l;
		this.h = h;
	}

	@Override
	public int compareTo(Chemical o) {
    	// 최고 보관 온도를 기준으로 내림차순 정렬.
		int diff = this.h-o.h;
        // 최고 보관 온도가 같은 경우 최저 보관 온도를 기준으로 내림차순 정렬.
		if(diff==0) {
			diff=this.l-o.l;
		}
		return diff;
	}
	
}

---

알게 된 점.

 

활동 선택 문제가 있을때 동일한 로직으로 짜면 쉽게 풀 수 있으니 꼭 알아 두기!!