백준 11000번 강의실 배정

문제

백준 11000번 강의실 배정 문제 링크

풀이 방법

위 문제를 보고 크게 2가지를 떠올릴 수 있었다. 바로 정렬과 우선순위 큐이다.

1. 입력값들을 배열에 저장

먼저 입력값들을 배열에 저장해야한다.

2. 배열을 정렬

이후 저장한 배열을 정렬해야한다. 그런데 여기서 중요한 점이 있다. 강의 시작 시각을 기준으로 정렬해야할지, 강의 종료 시각을 기준으로 정렬해야할지다. 사실 나는 직관적으로 강의 종료 시각을 기준으로 정렬해서 틀렸었다...
결론적으로 강의 시작 시각을 기준으로 정렬해야한다.

강의 시작 시각을 기준으로 정렬해야하는 이유
우리가 우선순위 큐를 어떻게 사용할지 매커니즘을 그림으로 그려보면 명확해진다.


<우선순위 큐를 사용하는 매커니즘>

1) 우선순위 큐에 정렬된 첫번째 수업을 삽입

2) 정렬된 두번째 수업의 시작시각과 우선순위 큐에서 가장 우선순위가 높은 수업의 종료시각을 비교

2-1) 종료시각 > 시작시각 -> 우선순위 큐에 해당 수업을 삽입

2-2) 종료시각 <= 시작시각 -> 우선순위 큐 요소를 뺀 뒤 해당 수업을 삽입

3) 2번 과정을 모든 요소에 대해 반복


결국 우리는 2-1에서 정렬된 배열의 시작시간을 우선순위 큐의 우선 요소와 비교한다. 따라서 우리는 강의 종료시각이 아닌 강의 시작시간으로 배열을 정렬해야하는 것이다.

따라서 배열을 강의 시작 시간을 기준으로 오름차순 정렬한다. 또한 만약 시작 시간이 같다면 종료시간으로 오름차순 정렬한다.

3. 우선순위 큐 사용

위의 예시에서 우선순위 큐를 어떻게 사용해야하는지는 보았다. 따라서 우리는 우선순위 큐의 우선순위는 종료시각임을 알 수 있다.

따라서 우선순위 큐를 생성한 뒤 우선순위를 정할 때 종료 시각이 작은 값이 우선순위를 갖게한다.

4. 우선순위 큐에 남은 요소 개수 출력

총 필요한 강의실의 개수는 우선순위 큐에 남은 요소 개수이다.
나는 처음에는 이게 이해가 안됐었다.

실행 중간에 100개의 수업이 동시에 있어서 우선순위 큐의 크기가 100까지 커졌다가 실행이 종료되기 전 수업들이 끝나서 마지막에 큐 크기가 5개면 답이 틀리지 않을까?

라는 의문이 있었기 때문이다.

하지만 이렇게 생각한다면 우리가 우선순위큐를 어떻게 사용할지 제대로 이해하지 못한 것이다. 우리는 우선순위 큐에서 요소를 뺄 때 종료 시각이 지났다고 무조건 빼는 것이 아니다. 종료 시각 이루에 시작하는 요소가 배열에 있을 때 우선순위 큐에서 요소를 뺀다.
따라서 모든 수업이 종료될 때 큐에 남아있는 요소들의 개수가 정답이 된다.

만약 이 글을 읽고도 이해가 안된다면 실제 사례를 그림을 그려서 생각해보면 금방 이해할 수 있을 것이다.

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		PriorityQueue<Class> pq = new PriorityQueue<>(
				(o1, o2) -> {
		            // 시작시간 오름차순 정렬, 시작시간 같다면 종료시간 오름차순 정렬
		            if (o1.end == o2.end) {
		                return o1.start - o2.start;
		            } else {
		                return o1.end - o2.end;
		            }
		        });
		int N = Integer.parseInt(st.nextToken());
		Class [] arr = new Class[N];
		// 입력 받기
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			arr[i] = new Class(start, end);
		}
		// 정렬하기
		Arrays.sort(arr);
		// 첫번째 요소 넣기
		pq.offer(arr[0]);
		
		for(int i=1; i<N; i++) {
			Class now = pq.peek();
			int nowEnd = now.end;
			if(nowEnd <= arr[i].start) pq.poll();
			pq.offer(arr[i]);
		}
		bw.write(pq.size()+"\n");
		bw.flush();
	}
	static class Class implements Comparable<Class>{
		int start, end;
		public Class(int start, int end) {
			this.start = start;
			this.end = end;
		}
		public int compareTo(Class c) {
			if(this.start == c.start) return this.end - c.end;
			return this.start - c.start;
		}
	}
}