백준 11000 파이썬

 

11000번: 강의실 배정

 

 

 

정답 코드

from sys import stdin
import heapq

read = stdin.readline

N = int(read())
heap = []
result = []
for _ in range(N):
    a, b = map(int, read().split())
    result.append((a, b))
result.sort() # time 정렬상태
heapq.heappush(heap, result[0][1]) # 첫번째 수업 끝나는 시간부터 들어가 있다.

for i in range(1, N):
    if heap[0] > result[i][0]: # 응 못들어가
        heapq.heappush(heap, result[i][1])
    else: # 들어갈 수 있어
        heapq.heappop(heap)
        heapq.heappush(heap, result[i][1])

print(len(heap))

 

 

오답 코드 (시간복잡도 X)

문제에서 N이 최대 200,000까지 치솟을 수 있다고 했다. 이런 경우엔 중첩 반복문으로는 답에 접근할 수 없다. 

한번의 for 문으로 끝내야한다. 

나는 기껏 heapq 로 heap 을 만들어놓고, 그 내부에서 for 문을 한번 더 돌렸다. 

heap[0] 를 사용하면, 굳이 heapq.heappop()을 하지 않더라도 자연스럽게 내가 원하는 값을 나타내어 비교할 수 있다.

-

while heap 을 조건으로 하여, heap 을 모두 소진할 때까지 비교를 진행했다. 그러고선 result 리스트의 길이로 답을 구하려했다.

반면 정답 코드에선 heap 의 길이를 기준으로 정답 코드를 구했다. 이 부분이 정답과 가장 큰 차이였다. 

from sys import stdin
import heapq

read = stdin.readline

N = int(read())
heap = []
result = []

for _ in range(N):
    a, b = map(int, read().split())
    heapq.heappush(heap, (a, b))
start, end = heapq.heappop(heap)
result.append([end])

while heap:
    pops = heapq.heappop(heap)
    for i in range(len(result)):
        if result[i][-1] <= pops[0]:
            result[i].append(pops[1])
            break
    else:
        result.append([pops[1]])


print(len(result))