[Java] BOJ11000, 백준 - 강의실 배정

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

11000번: 강의실 배정

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	11315	3365	2399	29.436%

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

 

출력

강의실의 개수를 출력하라.

 

 

우선 이 문제를 풀기 전에 백준의 회의실 배정(https://www.acmicpc.net/problem/1931) 문제를 풀어보는 것을 추천한다.

 

<풀이>

문제에서 강의의 시작시간과 종료시간이 주어지지만, 우리가 집중해야 할 것은 종료시간이다.

다음 강의가 시작되기 전에, 이전의 강의가 종료되어야만이 해당 강의실을 계속해서 사용할 수 있는 것이다.

그래서 우선 강의들을 강의 시작 시간을 기준으로 강의들을 정렬해주고, 이전 강의들의 종료 시간만을 저장해서 순서대로 비교해주면 된다. 

1. 강의들을 시작시간 순서대로 정렬해준다.
2. 이전 강의의 종료 시간을 기준으로,
   1. 같은 강의실에서 강의할 수 있을 경우에 강의 종료시간을 갱신해준다.
   2. 같은 강의실에서 강의할 수 없는 경우(이전 강의를 종료하는 시간이 현재 강의를 시작하는 시간보다 늦는 경우)에는 강의실을 하나 추가해서 새로 강의 종료시간을 저장한다.
3. 추가된 강의실의 갯수를 출력한다.

사이트의 예제로 예시를 들어보자.

첫 번째 수업은 1시에 시작해서 3시에 끝난다.

시작 시간은 순서대로 정렬되어있기 때문에, 다음 수업 시작도 현재 수업시작시간보다 크거나 같을 것이다.

따라서 종료 시간만 저장해준다. 3시

강의 시작을 2시에 해야하는데, 이전 강의 중 가장 빠른 종료시간이 3시기때문에 같은 강의실에서 진행할 수 없다.

따라서 새 강의실에서 진행해주고, 종료 시간만 저장해준다. (3시/4시 저장)

강의 시작시간: 3시인데, 3시에 종료하는 강의가 있기 때문에 이 강의실에서 이어서 한다.

기존 강의실의 종료 시간을 갱신해준다.(5시/4시 저장)

 => 총 강의실 2개 사용

 

 

오답풀이

처음에는 이 문제를 배열을 이용하려 풀으려고 했다.

하지만 배열을 이용하면 한 가지 문제가 있는데, 이전 강의들의 종료시간을 비교하려고 할 때, 강의실의 종료시간을 일일히 비교해줘야 한다는 것이다.

그러면 N의 입력범위가 200,000이고, 최악의 경우 강의실을 200,000만개 쓰게 되는데

그렇다면 시간복잡도는 O(N!)로 대충 계산해봐도 1초를 훌쩍 넘게된다. (알면서도 구현해본 나,,, 실제로 아래 코드로 시간초과가 떴다..)

loop: for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= cnt; j++) {
				// 현재 강의의 시작 시간이 room[cnt]보다 크다면
				if (lecture[i][0] >= room[j]) {
					// 배열의 값을 강의 종료시간으로 변경
					room[j] = lecture[i][1];
					continue loop;
				}
			}
			// 현재 사용중인 강의실에서 가능한 경우의 수를 찾지 못했을 때는
			// 어쩔 수 없이 새 강의실을 사용해야 한다.
			cnt++;
			room[cnt] = lecture[i][1];
		}

 

그렇다면 이 문제를 어떻게 해결할 수 있을까?

바로 우선순위 큐(Priority Queue)를 이용하면 된다.

우선순위 큐를 이용하면 노드들을 우선순위에 따라서 자동으로 정렬할 수 있다.

우선순위 큐의 시간복잡도는 O(log2N)이라고 한다.우리는 N개의 강의가 있고, 우선순위 큐의 삽입/삭제 과정이 일어난다고 하더라도 시간복잡도는O(N*log2N)이다.최댓값인 N=200,000기준으로 계산하더라도 350만으로 시간 내에 충분히 해결 가능하다.

 

그렇다면 우선순위 큐를 이용한 풀이를 생각해보자.

위에서 room[] 배열 대신 PriorityQueue를 이용해주면 해결할 수 있다.

room[j]를 갱신해주는 작업 대신 PriorityQueue에서 기존의 데이터를 poll()하고 다시 add()하면 된다.

cnt를 추가하는 작업은 단순하 PriorityQueue에 add()만 해주면 된다.

그럼 바뀐 코드를 보자

pq.add(lecture[0][1]);
		for (int i = 1; i <= n; i++) {
			// 현재 강의의 시작 시간이 peek값보다 크다면
			if (lecture[i][0] >= pq.peek()) {
				// 원래 있던 시간을 빼고 새 종료시간으로 업데이트
				// 정렬되어있기 때문에 이런식으로 해도 괜찮은것
				pq.poll();
				pq.add(lecture[i][1]);
				continue;
			}
			// 현재 사용중인 강의실에서 가능한 경우의 수를 찾지 못했을 때는
			// 어쩔 수 없이 새 강의실을 사용해야 한다.
			pq.add(lecture[i][1]);
		}

참 쉽죠?

pq의 peek()값이랑만 비교해도 되는 이유는 PriorityQueue라서,,, 가장 작은 종료시간이 peek값에 위치하게 된다.

 

 

전체 소스코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 입력부
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int[][] lecture = new int[n + 1][2]; // 0: 시작시간, 1: 끝시간
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			lecture[i][0] = Integer.parseInt(st.nextToken());
			lecture[i][1] = Integer.parseInt(st.nextToken());
		}

		// 어떤 강의의 끝 시간과 끝 시간이 같은 경우를 우선으로 체크한다.
		// 완전히 같지 않은경우, 끝 시간 + 1부터 끝까지 체크한다.
		// 시작하는 강의를 발견한 경우, 그 강의가 끝나는 시간을 저장

		// 만약 강의가 끝나기 전에 새 강의가 시작하는 경우, ProrityQueue에 삽입
		// 그러면 종료시간이 자동으로 정렬되기 때문에, pq의 peek값만 가지고 비교해도 된다.

		// 배열을 먼저 정렬해준다.
		Arrays.sort(lecture, Comparator.comparingInt(o1 -> o1[0]));

		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		pq.add(lecture[0][1]);
		for (int i = 1; i <= n; i++) {
			// 현재 강의의 시작 시간이 peek값보다 크다면
			if (lecture[i][0] >= pq.peek()) {
				// 원래 있던 시간을 빼고 새 종료시간으로 업데이트
				// 정렬되어있기 때문에 이런식으로 해도 괜찮은것
				pq.poll();
				pq.add(lecture[i][1]);
				continue;
			}
			// 현재 사용중인 강의실에서 가능한 경우의 수를 찾지 못했을 때는
			// 어쩔 수 없이 새 강의실을 사용해야 한다.
			pq.add(lecture[i][1]);
		}

		System.out.println(pq.size());
	}

}