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

문제

---

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=99&sfl=wr_subject&stx=%EB%83%89%EC%9E%A5%EA%B3%A0 

JUNGOL

 

풀이

---

전형적인 그리디 문제

N개씩 최저 보관 온도 xi와 최고 보관 온도 yi 가 입력된다.

문제에서는 모든 화학물질을 보관할 수 있는 냉장고의 수를 구하는 것이 목적이다.

 

문제 접근 방법은 다음과 같다.

1. 최고온도 yi를 기준으로 오름차순 정렬한다. (xi, yi 배열 )
2. 첫번째 화학물질의 최고온도를 maxDegree라는 변수에 할당한다
3. 두번째 화학물질 부터 최저온도와 maxDegree값을 비교한다.
4. 만약 최고온도 maxDegree와 다음 화학물질 최저온도보다 작다면 (즉, 해당 냉장고 온도에 맞지않는 화학물질이 들어오면)
5. 냉장고 하나가 더 필요하므로 +1 카운트

 

아래는 위의 접근과정을 나타낸 것이다. 

이차원 배열이므로 2번째 인덱스를 정렬할 것이면 람다식, compare 재정의를 통해 기준점을 정해주어야 한다.

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

public class JO_1828 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][2];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
//		Arrays.sort(arr, new Comparator<int[]>(){
//
//			@Override
//			public int compare(int[] o1, int[] o2) {
//				return Integer.compare(o1[1], o2[1]);
//			}
//		});
		
		Arrays.sort(arr, (o1,o2)-> (o1[1] - o2[1]));
		
		int cnt = 1;
		int maxDegree = arr[0][1];
		for (int i = 1; i < n; i++) {
			if(maxDegree < arr[i][0]) {
				maxDegree = arr[i][1];
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

메모리: 28,704 KB
실행시간: 95 ms
코드길이: 1012 B