[백준]11000(파이썬) - 강의실 배정

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

• 이 문제는 맨 처음 dictionary를 이용해서 구현해서 몇 개의 테스트 케이스는 통과했지만, 도저히 시간 초과를 해결할 수 없어서 결국 어떤 유형의 문제인지 봤습니다. 최소 힙 이라니... 생각지도 못했네요.
  하지만 곰곰이 생각해보니까 이거 여기서 시간 초과 났을 게 분명한데... 했던 부분을 최소 힙으로 풀어낼 수 있었던 것 같습니다.
• 이 문제의 핵심은 빨리 시작하는 수업 부터 순서대로 비교하고, 그 수업의 끝나는 시간과 다음으로 빨리 시작하는 수업의 시작 시간을 어떻게 효율적으로 비교할 수 있냐? 의 문제입니다.
• 먼저 classTime 이라는 리스트에 수업들의 정보를 입력받습니다.
• 다음으로는 시작하는 시간이 빠른 순서대로 수업들을 정렬시켜줍니다.
• 여기서부터가 중요한데요, 끝나는 시간들을 모아놓고 거기서 가장 빠른 시간을 for문마다 추가하고, 비교해야 한다고 생각했을 때 이 부분을 heapq를 이용한 최소 힙으로 구현해주면 됩니다.
• 그럼 heaq안에는 언제 추가가 되어야 하고 언제 빼줘야 할까요? 강의실이 필요한 경우는 끝나는 정렬 했을 때, 끝나는 시간보다 시작하는 시간이 빠른 경우 추가가 되어야 합니다.
• 위 조건들을 고려해서 문제를 풀면 아래와 같습니다.

 

import sys, heapq
input = sys.stdin.readline

n = int(input())
endTime= []
classTime = []
for i in range(n):
    start,end = map(int,input().split())
    classTime.append((start,end))

# 이문제 핵심은 끝나는 시간하고 시작하는 시간을 비교하는 것
# 시작하는 시간을 오름차순으로 정렬해준다. 그러면? 끝나는 시간만 비교하면 되는데
# 끝나는 시간도 끝나는 순서대로 비교해야하는데  모든 강의 끝나는 시간을 비교할 순 없다.
classTime.sort()

heapq.heappush(endTime,classTime[0][1])
cnt = 1
for i in range(1,n):
    # 언제추가?
    # 강의실이 필요한 경우는 끝나는 정렬 했을 때, 끝나는 시간 보다 시작하는 시간이 빠른 경우 추가가 되어야 하고
    # 끝나는 시간 보다 느리면 한 강의실에서 수업을 할 수 있다.
    if classTime[i][0] < endTime[0]:
        heapq.heappush(endTime,classTime[i][1])
        # 그냥 endTime length로 해도 될듯
        cnt += 1
    else:
        heapq.heappop(endTime)
        heapq.heappush(endTime,classTime[i][1])

print(cnt)

 

아래는 dictionary를 이용해서 풀었던 풀이인데, 코딩 테스트에서 in을 사용하는 건 효율성 문제에 치명적일 수 있습니다.

 

n = int(input())
dict = {}
endTime= []
for i in range(n):
    start,end = map(int,input().split())
    if start in dict.values():
        list_of_key = list(dict.keys())
        list_of_values = list(dict.values())    
        a = list_of_values.index(start)
        dict[list_of_key[a]] = end  
    else:
        dict[start] = end