11000

날짜 : 2022. . 

사용 언어 : python

 

문제

 

 

코드

import sys
import heapq

n = int(sys.stdin.readline())
cl = []
room = []

for i in range(n):
    cl.append(list(map(int, sys.stdin.readline().split())))
cl.sort(key = lambda x : x[0]) # 시작시간 순서로 sort

heapq.heappush(room, cl[0][1]) # 첫 강의의 종료시간 push
for i in range(1, n):
    if cl[i][0] < room[0]: # 강의실이 사용중인 경우
        heapq.heappush(room, cl[i][1])
    else: # 기존강의실 사용 가능
        heapq.heappop(room)
        heapq.heappush(room, cl[i][1]) # push와 동시에 sort되어 저장

print(len(room))

 

 

알게된 점

- 수업을 저장한 cl 리스트와 강의실의 각 종료시간을 저장한 room 리스트를 만들었다.

- 그리고 시작시간과 종료시간을 입력받은 후 시작시간을 기준으로 오름차순으로 정렬했다.

- 이후 우선순위 큐를 이용해 첫 강의의 종료시간을 입력했고 for문으로 강의실을 추가해야 하는 경우(해당강의 시작시간이 가장 빨리 끝나는 사용중인 강의실의 종료시간보다 이른 경우)와 그렇지 않은 경우 두 가지 케이스로 분리하여 추가와 갱신을 적용함으로써 문제를 해결할 수 있었다.

- 한 30분정도 고민해서 나름 문제를 풀어봤지만 어떻게 강의실의 빈 시간을 채울지 아이디어가 떠오르지 않았다.
- 그래서 구글링을 해본 결과 우선순위 큐(힙)를 이용해 풀이하는 문제라는 것을 알게 되었고 heapq 모듈 또한 알게되었다.

- 기본적으로 알고 있던 자료구조 개념이지만 이렇게 코딩테스트에 사용하여 문제를 해결하는 것은 처음이었다.

 

 

참고 사이트

- https://suyeon96.tistory.com/31

[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)

- https://velog.io/@slbin-park/백준-11000번-강의실-배정-파이썬