[Baekjoon 11000 / Python / 골드5] 강의실 배정

문제

 

그리디, 우선순위 큐 문제이다.

 

# 골드5 -> 그리디, 자료구조, 정렬, 우선순위 큐

import heapq

import sys

input = sys.stdin.readline

N = int(input())

data = [list(map(int, input().split())) for _ in range(N)]

data.sort()

# 첫번째 시작하는 수업의 종료시간을 저장

# 종료시간은 우선순위가 됨

pq = []

heapq.heappush(pq, data[0][1])

for i in range(1, N):

    # 다음 수업과 진행중인 수업이 중복되지 않을 경우 진행중 수업 빼기

    if data[i][0] >= pq[0]:

        heapq.heappop(pq)

    heapq.heappush(pq, data[i][1])

print(len(pq))

 

우선 입력받은 수업들을 "시작 시간" 순으로 정렬한다.

 

반복문을 진행하며 시작 시간 순으로 정렬된 수업의 "종료 시간"을 큐에 넣는다. 최소 힙이므로 자동으로 종료 시간이 가장 이른 수업이 가장 앞에 오게 된다.

 

만약 이후 수업의 "시작 시간"이 큐의 첫번째에 있는 종료시간(가장 빨리 끝나는 수업)과 겹치지 않는다면, 큐에서 수업을 뺀 후 새로운 수업을 넣는다. 만약 겹친다면, 큐에서 수업을 빼지 않고 새로운 수업을 추가만 한다. 즉 수업이 겹칠 경우 큐의 길이가 증가한다. 이렇게 반복하여, 마지막으로 큐의 길이를 출력하면 된다.

 

내가 매우 헷갈렸던 점, 어째서 마지막 큐의 길이를 출력하는 것이지? 매 반복마다 큐의 길이를 측정하여 최대 길이를 갱신한 후 그것을 출력해야 하는 것 아닌가? 라고 생각해서 한참을 들여다 봤지만 너무 헷갈려서 잘 이해가 안됐다.

 

여기서 중요한 것은, 이 로직에서 큐의 길이는 "늘어나면 늘었지 절대 줄지 않는다" 는 것이다. 사실 로직 보면 당연히 그렇긴 한데, 애초에 pop 하는 조건은 "다음 수업이 존재하고, 그 수업이 가장 빨리 끝날 수업과 겹치지 않을 경우"이다. 이 조건이 만족되면 "단 한개"의 수업만 큐에서 뺀다.

 

즉 겹치지 않는 다음 수업이 있을 경우, 그 수업 한 개당 하나의 수업만을 큐에서 뺀다. 따라서 큐의 길이는 줄어들지 않고 최대치로 유지된다. 이 반복문이 만약 수업의 개수(N)만큼 반복하는 게 아닌, 수업 시간을 기준으로 반복했다면 최대값을 갱신해야 했을 것이다.

 

결과