[BOJ][🟡5][백준#19598] 최소 회의실 개수

문제 출처

BAEKJOON Online Judge #19598

문제

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

입력

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

출력

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

예제

예제 1

입력

3
0 40
15 30
5 10

출력

2

예제 2

입력

2
10 20
5 10

출력

1

My Sol

import sys
input = sys.stdin.readline
from heapq import heappop, heappush

def main():
    def make_H():
        H = []
        for _ in range(N):
            s, e = map(int, input().split())
            heappush(H, (s, e))
        return H

    def count_place():
        cnt = 1
        K = []
        s, e = heappop(H)
        heappush(K, e)
        while H:
            s, e = heappop(H)
            if K[0] > s:
                cnt += 1
            else:
                heappop(K)
            heappush(K, e)

        return cnt

    N = int(input())
    H = make_H()
    return count_place()

print(main())

heapq를 사용해 문제를 해결할 수 있었다.

1. 각 회의실 일정을 입력으로 받는데, 이를 heapq에 담는다. (시작시간, 종료시간)으로 오름차순 정렬된다. 이를 반환하는 make_H 함수를 작성한다.
2. 이렇게 만들어진 H heapq에서 가장 빨리 시작할 회의를 매번 꺼내며 확인을 진행하는데, 이를 count_place 함수에서 진행한다.
3. count_place 함수 내에서는 heapq K를 추가로 제작하는데, 이 heapq는 종료시간을 빠른 순으로 저장하는 heapq이다. 즉, H에서 꺼낸 회의실 일정의 시작시간이 K의 가장 빠른 종료시간의 회의보다 작거나 같은지, 혹은 큰지에 따라 분기 처리를 한다.
4. 만약 K의 가장 작은 값, 즉 가장 빨리 끝나는 회의 시간이 H에서 이제 꺼낸 회의 일정의 시작시간보다 크면 현재까지 빌린 강의실로는 커버할 수가 없는 상황이므로 강의실을 하나 더 빌린다고 감안하여 cnt를 1 더 늘려주고 e를 K에 넣어준다.
5. 반대로 K의 가장 작은 값이 H의 s보다 작으면, 현재 등록해야하는 회의일정에 가용한 회의실을 K에서 제공할 수 있는 것이므로 단순히 K의 가장 작은 값을 heap pop을 이용해 제거하고, 신규 등록된 회의의 종료시간 e를 K에 추가한다. cnt의 증가는 필요하지 않다.
6. 이러한 과정을 H가 빌 때까지 하고, 누적된 cnt를 반환, 이를 최종적으로 출력해주면 되겠다.

결과

맞았습니다!!

모범답안

출처

import sys, heapq
input = sys.stdin.readline

N = int(input())
schedules = sorted([list(map(int, input().split())) for _ in range(N)])
h = []
for start, end in schedules:
    if h and h[0] <= start:
        heapq.heappop(h)
    heapq.heappush(h, end)

print(len(h))

연산시간은 같지만 코드길이가 짧은 코드를 분석하려 한다. 우선 회의 일정을 heapq에 담지 않고 list에 담아 sort했다. heapq의 정렬은 O(nlogn)이고, list의 정렬은 O(n2)이지만, 은근히 list의 정렬이 꽤나 빠르다.

가장 큰 차이는 for문의 과정인데 어차피 cnt를 따로 설정해줄 필요 없이 heapq의 최솟값과의 비교로 heap에서 pop을 하면 cnt는 1 줄어들게 되는데, 이를 잘 활용한 풀이인 것 같다.