99클럽 코테 스터디 _ 20일차 TIL (우선순위 큐)

 

< 문제 >

[백준] 19598. 최소 회의실 개수 / 골드5

---

< 풀이 >

코드 변수 정의

• meetings : 각 회의의 시작 시간과 종료 시간을 담은 리스트
• pq : 우선순위 큐
• start, end : 회의 시작 시간, 회의 종료 시간

---

Priority Queue
시간복잡도 : O(N logN)

import heapq

def meeting_room():
    N = int(input())
    meetings = [list(map(int, input().split())) for _ in range(N)]
    meetings.sort()  # 회의 시작 시간을 기준으로 정렬
    pq = []  # 우선순위 큐 생성
    heapq.heappush(pq, meetings[0][1])  # 1번째 회의 종료 시간을 힙에 push
    
    for i in range(1, N):
        start, end = meetings[i]
        if pq[0] <= start:  # 기존 회의가 끝났으면 pop
            heapq.heappop(pq)
        heapq.heappush(pq, end)  # 현재 회의를 새로운 회의실에 배정
    return len(pq)  # pq에 남아있는 원소의 개수가 필요한 회의실 개수

print(meeting_room())

 

 

 

풀이 방식

1. 회의 시간 정렬
   • 회의를 시작 시간 기준으로 오름차순 정렬한다.
   • 시작 시간이 빠른 순서대로 회의를 배정해야 효율적인 스케줄링이 가능하다.
2. 우선순위 큐 활용
   • 최소 힙(min-heap)을 사용하여 현재 진행 중인 회의의 종료 시간을 관리한다.
   • 힙의 최상단에는 항상 가장 빨리 끝나는 회의의 종료 시간이 위치하게 된다.
3. 회의실 배정
   • 정렬된 회의를 하나씩 순회하면서 pq에 추가하거나 기존 회의실을 재사용한다.
     • pq[0]은 현재 가장 빨리 끝나는 회의의 종료 시간을 의미
   • 만약 현재 회의의 시작 시간이 기존 회의실 종료 시간보다 크거나 같다면, 기존 회의실을 재사용(heapq.heappop(pq))한다.
     • 새로운 회의를 배정하기 위해 종료 시간을 heapq.heappush(pq, end)로 힙에 추가
   • 마지막에 pq에 남아있는 원소의 개수가 필요한 최소 회의실 개수가 된다.

---

< 회고 >

🤔 💭_

처음에는 우선순위 큐를 사용하지 않고 회의의 종료 시간을 기준으로 정렬하여 시간을 비교하는 방식으로 풀이했다. 근데 이렇게 할 경우 다음과 같은 테스트 케이스를 통과하지 못하는 것을 확인했다.

 

[잘못된 풀이] 종료 시간을 기준으로 정렬한 처음 풀이 방식의 문제

예시)

N = 4
meetings = [[2, 3], [1, 10], [13, 15], [5, 20]]
meetings.sort(key=lambda x:x[1])
# print(meetings)
# [[2, 3], [1, 10], [13, 15], [5, 20]]

cnt = 1  # 초기 회의실 한 개
start, end = -1, -1  # 현재 회의 시작 시간, 종료 시간

for meeting in meetings:  # 회의 시간 순회하며 확인
   ns, ne = meeting  # 새로운 회의 시작 시간, 종료 시간
   if end <= ns:  # 현재 회의 종료 시간보다 새로운 회의 시작 시간이 큰 경우
       start, end = meeting  # 현재 회의 시간을 새로운 회의 시간으로 갱신한다.
   else:  # 현재 회의 종료 시간보다 새로운 회의 시작 시간이 작은 경우
       cnt += 1  # 새로운 회의실을 잡는다. (cnt + 1)
       start, end = meeting  # 마찬가지로 현재 회의 시간을 새로운 회의 시간으로 갱신한다.

# print(cnt)  # 전체 회의실 개수는 3개가 된다.
# 3  # 틀린 답

틀린 이유

위 예시의 정답은 2개여야 한다.
1번 회의실   :   [2, 3], [5, 20]
2번 회의실   :   [1, 10], [13, 15]

근데 내가 푼 풀이의 결과는 3개의 회의실을 생성한다.
1번 회의실   :   [2,3]
2번 회의실   :   [1, 10], [13, 15]
3번 회의실   :   [5, 20]


해결 방법

그래서 시작 시간을 기준으로 정렬한 후, 우선순위 큐로 종료 시간을 활용해야 한다는 것을 생각하게 되었다.

새로운 회의 시작 시간이 현재 우선순위 큐에 있는 최소 값보다 큰 경우 이 값을 pop 한 후 새로운 회의 종료 시간을 push 한다.
(pop 한 후 push 하는 과정은 같은 회의실을 재사용하는 것을 의미하게 된다. 따라서, 회의실 개수는 변화없다.)

새로운 회의 시작 시간이 현재 우선순위 큐에 있는 최소 값보다 작은 경우 새로운 회의 종료 시간을 push 한다.
(종료 시간만 push 하는 과정은 새로운 회의실을 사용하는 것을 의미하게 된다. 따라서, 회의실 개수를 한 개 늘린다.)