반응형

-풀이

import sys, heapq
input = sys.stdin.readline
cnt = 0
count = []
answer = []
N = int(input())
for i in range(N):
  a = list(map(int,input().split()))
  answer.append(a)
answer.sort()
for j in range(len(answer)):
  if len(count) == 0:
    #회의 끝나는 시간 count에 저장
    heapq.heappush(count, answer[j][1])
    cnt += 1
  else:
    #회의 끝나는 시간보다 시작시간이 빠르면 
    if answer[j][0] < count[0]:
      heapq.heappush(count, answer[j][1])
      cnt += 1
    else:
      heapq.heappop(count)
      heapq.heappush(count, answer[j][1])
print(cnt)
  
  -풀이 설명

바로 전에 풀었던 콘센트 문제와 비슷한 유형의 문제로, 강의가 끝나는 시간을 count리스트에 담고 각 각 수업 시작시간과 비교하여  강의가 끝나는 시간보다 시작시간이 더 빠를경우 강의실을 하나 더 만들고, 반대라면 강의가 끝나는 시간을 갱신해준다.

ps.  if answer[j][0] < count[0]: 이부분이 약간 헷갈렸다. 왜냐하면 count[0] 값만 계속 가져오기 때문이다. 그러나 조금씩 실험해보면서 생각해보니 heapq를 이용하면 heappush를 할 때 자동적으로 이진트리 최소힙으로 정렬이 되기 때문에 항상 count[0]값과 비교해도 최소의 끝나는 시간으로 대조할 수 있었다.

+ Recent posts