[백준] 11000번: 강의실 배정

문제

https://www.acmicpc.net/problem/11000

문제는 최소의 강의실을 사용하도록 시간표를 만들도록 하면 해결

어떻게 접근해야되나 모르겠는데.. 찾아보니 그리디 알고리즘을 이용하면 된다고 한다

알고리즘

그리디 알고리즘이란?
최적해를 구하는데 사용되는 근사적인 방법
지금 처한 상황에서는 최선의 선택을 한다
그렇다고 결과적으로 최선이 아닐 수 있다

최소의 강의실을 사용하도록 해야하므로 강의 시간을 기준대로 실행하면 될 것 같다

따라서 시작시간이 빠른 순서대로 정렬

코드

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

public class Baekjoon11000_2 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		// 시작 시간과 끝나는 시간을 저장하는 배열 arr
		int[][] arr = new int[N][2];
		
		for (int i=0 ; i<N ; i++) {
			String str[] = br.readLine().split(" ");
			arr[i][0] = Integer.parseInt(str[0]);
			arr[i][1] = Integer.parseInt(str[1]);
		}
		
		// override
		// 시작시간을 기준으로 정렬, 혹시 시작 시간이 같다면 끝나는 시간이 더 빠른 것으로 정렬
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0]) return o1[1] - o2[1];
				return o1[0] - o2[0];
			}
		});
		
		// 처음 배정되는 강의실은 한개
		int result = 1;
		// 끝나는 시간을 기준으로 다음 강의 배정
		int prev = arr[0][1];
		
		for (int i=1 ; i<N ; i++) {
			// 만약 끝나는 시간이 다음 강의보다 늦다면 강의실 추가
			if (prev > arr[i][0]) {
				result ++;
			}
			// 전 강의가 먼저 끝난다면 강의 끝나는 시간을 다시 업데이트
			else {
				prev = arr[i][1];
			}
		}
		System.out.println(result);
	}

}

마무리

오버라이딩도 나오고.. 정렬도 다시 해야되고 이러니까 좀 어지러웠다
그리디 알고리즘도 처음 보는데 좀 더 공부해야 할 것 같다
자바에 생각보다 내가 활용하지 못하는 클래스들이 많아서 더 봐야할 듯