[99클럽 코테스터디 20일차 TIL / 백준] 19598 - 최소 회의실 개수 (그리디, 정렬, 우선순위큐)

99클럽 코테스터디 20일차 TIL  
KeyWord : 그리디, 정렬, 우선순위큐

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

입력

첫째 줄에 배열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231−1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최소 회의실 개수를 출력한다.

 

---

 

풀이

그리디 하면 대표적인 문제로 뽑히는 회의실 문제이다. 내가 공부했던 알고리즘 서적에서도 보았던 기억이 있다.

간단히 로직만 빠르게 정리해보자.

1. 회의 시작 시간 오름차순으로 회의를 정렬한다.
   • 정렬 시 종료 시간은 신경쓰지 않아도 된다.
2. 시작 시간이 빠른 회의부터 회의실을 배정한다.
   • 회의를 배정하기 전, 현재 배정할 회의의 시작 시간 이전에 종료된 회의가 있는지 확인한다.
     • 종료된 회의가 있다면, 그 회의실을 배정한다.
     • 종료된 회의가 없다면, 새로운 회의실을 배정한다.
3. 모든 회의를 배정할 때까지 2번을 반복한다.

이 문제는 시간 제한이 2초로 굉장히 넉넉한 편이라 효율성을 많이 고려하지 않아도 통과할 수 있다. (자바라면 5초)

List<Integer> meetingList = new ArrayList<>();
for (int i = 0; i < N; i++) {
    boolean found = false;
    for (int j = 0; j < meetingList.size(); j++) {
        if(meetingList.get(j) <= meetings[i][0]) { // 기존 회의실에 배정이 가능한 경우
            meetingList.set(j, meetings[i][1]);
            found = true;
            break;
        }
    }

    if(!found) { // 기존 회의실에 배정이 불가능한 경우
        meetingList.add(meetings[i][1]);
    }
}

그래서 이렇게 $O(N^2)$의 비효율적인 완전탐색을 활용하여도 통과는 할 수 있다.

4.4초로 아슬아슬하게 통과가 된다. 그리디하게 풀 수만 있다면 통과가 되게끔 설정된 문제인 듯했다.

하지만 이렇게 끝내기에는 뭔가 찝찝하니 코드를 조금 더 개선해 보자.

종료된 회의가 있는지 확인하는 부분에서 시간을 줄일 수 있을 듯하다. 현재는 meetingList에서 완전탐색을 진행하여 일일히 비교를 진행하고 있다. 여기서 가장 빨리 종료되는 회의를 바로 빼낼 수만 있으면, 완전탐색에 낭비되는 시간이 사라질 것이다.

즉, 우선순위큐를 사용하면 된다. 이렇게 하면 $O(N^2)$이던 코드를 $O(N)$으로 개선할 수 있다.

4432ms → 612ms로 크게 성능을 향상시켰다.

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.*;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

        int N = Integer.parseInt(br.readLine());  
        int[][] meetings = new int[N][2];  

        for (int i = 0; i < N; i++) {  
            StringTokenizer stk = new StringTokenizer(br.readLine());  
            meetings[i][0] = Integer.parseInt(stk.nextToken());  
            meetings[i][1] = Integer.parseInt(stk.nextToken());  
        }  

        Arrays.sort(meetings, (o1, o2) -> {  
            if(o1[0] == o2[0]) return o1[1] - o2[1];  
            return o1[0] - o2[0];  
        });  

        PriorityQueue<Integer> pq = new PriorityQueue<>();  
        pq.add(meetings[0][1]);  
        for (int i = 1; i < N; i++) {  
            if(pq.peek() <= meetings[i][0]) {  
                pq.poll();  
            }  
            pq.add(meetings[i][1]);  
        }  

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

 

---

 

여담

완전탐색 코드를 제출했을 때 4432ms로 통과가 되길래 "이게 왜 통과되지?" 했었다. 문제에 명시된 시간 제한 2초를 확실하게 뛰어넘었기 때문이다.

https://help.acmicpc.net/language/info

찾아보니 자바 같이 무거운 언어는 조금 시간 제한과 메모리 제한에 더 보너스가 있다고 한다.

즉, 이 문제의 경우에는 $2 \times 2 + 1$인 5초가 주어진 셈이다.