[백준 1374 파이썬] - 강의실

📌 문제

💯 정답

import sys
import heapq
input = sys.stdin.readline

N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]
l.sort(key=lambda x: x[1])

mh = []
cnt = 0
for i in l:
    while mh and mh[0] <= i[1]: # 가장 일찍 끝나는 시간보다 시작 시간이 크면
        heapq.heappop(mh)       # mh에서 가장 작은 원소 pop & return
    heapq.heappush(mh, i[2])    # mh에 i[2]=끝나는 시간을 추가
    cnt = max(cnt, len(mh))

print(cnt)

📝 설명

• 처음 생각은 정렬후 현재 강의 시작시간이 앞 강의 종료시간 중 가장 작은 시간보다 크면 카운트하지 않는 것이었다.
  어떤식으로 구현해야될지 모르겠어서 아래 블로그를 참고했다.
  내가 생각한 로직과 비슷했는데 heapq 를 사용하면 된다는 것을 알게됐다.

• 우선 시작시간을 기준으로 강의들을 정렬한다.

• 새리스트 mh에는 최소힙을 저장하는 리스트이다.
  만약 가장 일찍 끝나는 시간보다 시작 시간이 크면 일찍 끝나는 강의는 pop한다.
  그렇지 않거나 mh에 값이 없으면 끝나는 시간을 추가한다.
  
• 즉 mh에는 끝나는 시간이 들어있고 이 시간과 다른 수업의 시작시간을 비교해 겹치지 않으면
  전에 들어있던 강의를 pop하는 것이다.

• 그리고 매번 mh의 길이 즉 강의 수를 구해 그 중 가장 max값을 구하면 최소 강의실 수를 알 수 있다.

🔎 힙큐 (heapq)

👉 [Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

import heapq

heapq.heappop(heap)			# heap에 들어있는 값중 최솟값 pop & return , 값이 없으면 index error
heapq.heappush(heap, x)		# heap에 x 추가
heapq.heapify(list)			# list를 바로 heap으로 변환. O(n)

🙏 참고

👉 백준 온라인 저지, 자료구조 / 1374번: 강의실 (파이썬 / 백준 골드문제)