[Algorithm] 백준 BOJ 11000 강의실 배정 : python 파이썬 그리디 골드 5

Private 난이도 : ♥♥♥♥♡

11000번: 강의실 배정

import sys
import heapq

n=int(sys.stdin.readline())
time=list()
for i in range(n):
    s,t = map(int, sys.stdin.readline().split(' '))
    time.append((s,t))

time.sort() # 1차  sort
room=[0]

for s,t in time:
    if room[0] <= s:
        heapq.heappop(room)
    heapq.heappush(room, t) # 2차 sort

print(len(room))

백준 제출 버전

배운 점

• 처음에 생각했던 코드는 이런 방향이 전혀 아니었고 시간초과가 났었다.
  

  import sys
  n=int(sys.stdin.readline())
  time=list()
  room=list()
  for i in range(n):
      s,t = map(int, sys.stdin.readline().split(' '))
      time.append((s,t))
  
  time.sort()
  for s,t in time:
      if len(room)==0:
          room.append(t)
          
      else:
          diff=float('-inf')
          diff_j=-1
          for j,r in enumerate(room):
              now_diff=r-s
  
              if now_diff==0: # 수업 끝 직후 시작 -> 기존
                  diff_j=j
                  break
              elif now_diff>0: # 수업이 겹침 ->강의실 추가
                  continue
              elif now_diff > diff: # 수업이 안 겹침 ->기존
                  diff=now_diff 
                  diff_j=j # 차가 가장 작은 강의실로
  
          if diff_j==-1: # 강의실 추가 # 수업이 다 겹침
              room.append(t)
              # print('added room',room)
          else: # 기존 강의실에 이어서 수업
              room[diff_j]=t
              # print('existed room',room)
  # print(room)
  print(len(room))

  이렇게 풀게 된 이유는, 나중에 와서 깨닫게 되었지만 미래에 혹시 몰라 나오는 강의가 강의 중간에 들어갈 수 있다고 생각해서 시간 차이가 가장 작게 나는 강의실에 이어서 강의를 해야한다는 생각 때문이었다. 연산을 한 번 더 하는 결과를 낳았지만 틀린 결과를 내뱉지는 않았다. 하지만 시간초과 때문에 heapq를 사용할 수 밖에 없었다. 이 아이디어를 가지고 힙을 사용해 보았지만 여전히 시간초과가 나서 포기했다.
• 특히 내가 원하는 상황은 이것이었다
  <입력>
  5
  1 3
  1 4
  1 5
  1 6
  7 10
  <출력> 4
  강의간의 간격을 최소로 유지하기 위해서 7 ~ 10시의 강의를 무조건 4번에 넣어야 한다고 생각했는데 그게 아니었다.
  
• 이미 강의를 sort하면 미래에 어떤 강의가 들어올지 걱정하지 않아도 이미 정렬되어 들어갔기 때문에 걱정하지 않고 그냥 heap의 루트노드와 비교에서 넣어도 되는 것이었다. 말 그대로 넣기만 하면 되는 것이다. 이것을 깨닫지 못했었다는 것이 시간이 오래걸렸던 것 같다.