백준 11000 - 파이썬

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

11000번: 강의실 배정

문제 풀이

이 문제를 보고 가장 처음 떠올린 아이디어는 다음과 같다.

 

1. 먼저 시작시간 기준으로 정렬

2. 현재 강의의 끝나는 시간과 다음 강의의 시작 시간이 같거나 더 늦은 시간이 있는지 확인

3. 있다면 방을 카운트하고, 없다면 끝나는 시간과 시작 시간이 가장 근접한 강의 확인.

 

위 생각을 알고리즘으로 구현하고자 노력해 보았다. 처음에는 리스트로만 구현을 하다가 우선순위 큐를 사용하는 것이 좋을 거 같아 heapq라는 자료구조로 구현해 봤다. 1시간 반이 넘게 고민해 보았지만 답을 구하기 어려웠고, 결국 다른 사람의 풀이를 찾아보았다.

 

import heapq
import sys

n = int(sys.stdin.readline())

q = []

for i in range(n):
  start, end = map(int, sys.stdin.readline().split())
  q.append([start,end])

q.sort(key=lambda x : x[0])

room = []
heapq.heappush(room, q[0][1])

for i in range(1, n):
  if q[i][0] < room[0]:
    heapq.heappush(room, q[i][1])
  else:
    heapq.heappop(room)
    heapq.heappush(room, q[i][1])

print(len(room))

기본적으로 두번째 for문 위에 있는 room이라는 리스트에 가장 처음 수업의 끝나는 시간을 넣어주는 것까지는 같았다. 내가 구현해 내지 못한 부분은 이 부분이다.

for i in range(1, n):
  if q[i][0] < room[0]: # 현재 수업 끝나는 시간보다 다음 수업 시작시간이 빠르면
    heapq.heappush(room, q[i][1]) # 새로운 강의실 개설
  else:  # 현재 강의실에 이어서 강의 개최 가능
    heapq.heappop(room) # 새로운 수업으로 시간 변경을 위해 pop후 새 시간 push
    heapq.heappush(room, q[i][1])

room에는 현재 수업이 끝나는 시간이 담겨 있는데, 그 다음 수업의 시작시간과 비교하여 다음 수업의 시작시간이 빠르면 새로운 강의실을 개설하는 것이다.

 

나는 끝나는 시간과 시작 시간이 같거나 더 늦은 시간을 비교하여 새로운 강의실을 추가하고자 하였는데, 끝나는 시간과 시작 시간이 같다면 강의실을 추가할 필요가 없으므로 더 늦은 시간만 비교해도 되었던 것이다. 이 점이 내가 구현하는데 어려움을 줬던 점인것 같다. 정리하면, 새로운 강의실을 추가할 경우는 현재 수업의 끝나는 시간보다 시작시간이 빠른 강의일 때만이다. 따라서 이 경우에만 우선순위 큐에 추가해주면 되었던 것이다.

 

지금까지 그리디를 풀면서 느낀점은 조금만 더 생각을 다듬고 코드로 정리하면 풀 수 있는데, 아직까지는 이 부분이 가장 힘든점인거 같다. 이 벽을 뚫는다면 실력이 한층 더 오를 거 같다. 또한 자료구조를 적절히 사용하는 법 역시 숙달할 필요가 있어 보인다.