[99클럽 5기] 코딩테스트 스터디 20일차 TIL - 우선순위 큐

[Gold V] 최소 회의실 개수 - 19598

[문제 링크](https://www.acmicpc.net/problem/19598)

🗝️오늘의 학습 키워드 (Keyword)

• 그리디 알고리즘
• 우선순위 큐
• 정렬

---

💻본인의 언어로 내용 정리 (Today I Learned)

N개의 회의를 진행하기 위해 최소 회의실의 개수를 구해야 한다. 각 회의의 시작 시간과 끝나는 시간이 주어지고, 이를 이용해 회의 시간이 겹치지 않도록 하는 회의실의 개수를 구하는 문제이다.

 

회의의 시작 시간이 작을 수록 먼저 시작하는 회의고, 끝 시간이 클수록 늦게 끝나는 회의이다.

먼저 시작하는 회의를 기준으로 해당 회의의 끝나는 시간과, 다음 회의의 시작 시간을 비교하며 회의실의 개수를 카운트하는 알고리즘을 작성하면 될 것 같다.

 

이렇게 생각하고 설계를 해 보았다.

 

💡알고리즘 풀이

heap = []
heapq.heappush(heap, time_list[0][1]) # 처음 시작하는 회의가 끝나는 시간 삽입

for i in range(1, N):
    start, end = time_list[i] # 다음 회의 시작 시간과 끝 시간

    if (heap[0] <= start): # 이전 회의의 끝 시간이 다음 회의의 시작 시간보다 작을 경우
        heapq.heappop(heap) # 힙에서 제거 => 회의실을 비움

    heapq.heappush(heap, end) # 끝나는 시간을 회의실에 추가함으로써 회의실을 늘림
    
print(len(heap))

우선순위 큐를 활용하기 위해 힙을 생성하였다. 힙에는 각 회의의 끝 시간이 들어간다.

 

반복문을 통해 회의 시간 리스트를 돌며, 시작 시간과 끝 시간을 각각 start, end 변수로 받는다.

 

heap[0]에는 heap의 최상단, 즉 가장 먼저 시작한 회의의 끝 시간이다. 이와 현재 회의의 시작 시간을 비교하며 힙에서 제거를 한다. (회의실을 기준으로, 회의가 끝나고 다음 회의가 시작한 것이라 생각하면 편하다.)

 

heap의 크기는 곧 회의가 진행중인 회의실이 된다.

 

🗒️제출 코드

# 19598 최소 회의실 개수

import heapq

N = int(input())

time_list = [list(map(int, input().split())) for _ in range(N)]
time_list.sort(key = lambda x : x[0]) # 먼저 시작하는 순으로 정렬

heap = []
heapq.heappush(heap, time_list[0][1]) # 처음 시작하는 회의가 끝나는 시간 삽입

for i in range(1, N):
    start, end = time_list[i] # 다음 회의 시작 시간과 끝 시간

    if (heap[0] <= start): # 이전 회의의 끝 시간이 다음 회의의 시작 시간보다 작을 경우
        heapq.heappop(heap) # 힙에서 제거 => 회의실을 비움

    heapq.heappush(heap, end) # 끝나는 시간을 회의실에 추가함으로써 회의실을 늘림

print(len(heap))

---

💭오늘의 회고

복잡해 보이지만,  역시나 문제를 잘 읽어보면 쉽게 풀 수 있는 문제였다.

회의의 끝나는 시간을 기점으로 다음 회의의 시작 시간을 통해 회의실 여부를 판단하는 식의 접근으로 하였다면 쉽게 풀릴 문제일 것이다.

 

오늘로 99클럽 4주차가 끝이났다. 함께 할 날이 일주일이 채 남지 않았다.

 

지금까지 열심히 달려왔고, 남은 기간동안 멈추지 말고 끝까지 완주 해보자!

---

⬇️전체 소스코드⬇️

hanghae99/python_middler/20일차 최소 회의실 개수/최소 회의실 개수.py at main · Do-heewan/hanghae99