Solution

풀면 풀수록 느끼는 거지만, 그리디 알고리즘과 우선순위 큐는 관련이 깊은것 같다.

우선순위 큐는 특정 시점에서 최댓값 or 최솟값을 필요로 할 때 사용한다.

이 문제에서는 끝나는 시간들을 end라는 우선순위 큐(최소힙)에 저장하고, 다음 수업 시간이 이 루트노드의 수보다 작다면 강의실을 늘리는 방식으로 문제를 해결하였다.
(루트 노드에는 끝나는 시간 중에서 최솟값이 들어있으므로, 이 수보다 작은 수면 다른 강의실의 끝나는 시간과도 다 겹친다!!는 생각이 들었다..)

import sys, heapq
input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    heapq.heappush(arr, list(map(int, input().split())))
end = [0]
cnt = 1
for i in range(N):
    if arr[0][0] >= end[0]:
        heapq.heappop(end)
    else:
        cnt += 1
    heapq.heappush(end, arr[0][1])
    heapq.heappop(arr)
print(cnt)

풀이 과정

10
1 2
1 5
1 10
2 5
3 5
3 7
5 10
6 8
6 8
7 10

이라는 예제를 혼자 생각해보고, 이 상황에 대한 풀이 과정을 하나씩 직접 풀어가면서 '이 방식으로 코드를 작성해야 겠다!' 는 생각이 들었다.

• end라는 변수를 두려고 했지만, 강의실이 늘어나면 그만큰 end도 늘어날거니까 배열로 바꿈
• 'end에 있는 모든 수를 비교할 필요없이 가장 작은 수만 비교하면 되지 않나?' 라는 생각이 들어 end를 heapq을 통해 구현한 우선순위큐로 바꿔주었다.
• input을 모두 저장하는 arr는 오름차순 정렬을 한 배열로 구현해도 되고, 최소힙으로 구현해도 괜찮다는 생각이 들었지만 그냥 최소힙으로 구현했다. (배열 입력받고 다시 정렬해주기 귀찮아서,,)

후기

우선순위큐 문제를 자주 푸니까 점점 더 잘 활용할 수 있게 되는거 같다! 야호!