[python] 1374 - 강의실

1374번: 강의실 (acmicpc.net)

1374번: 강의실

 

전에 프로그래머스에서 비슷한 문제를 풀어봤는데

다시 풀어보려니 또 헷갈려서 정리를 해보려고 한다.

우선 이 문제는 우선순위 큐를 사용하여 쉽게 풀 수 있다.

 

최대한 많은 강의를 최대한 적은 수의 강의실을 사용하여야 하므로

그리디에 속한다고 볼 수도 있을 것 같다.

문제를 풀기 위해 고려해야 하는 것은 다음과 같다.

 

1. 여기서 강의번호는 무시해도 좋다.

2. 강의 시작 시간과 종료 시간을 묶어서 우선순위 큐에 넣는다. -> 강의 시작 시간이 기준이 된다.

3. 강의실 개수를 세기 위한 우선순위 큐를 하나 더 만든다.

4. 이전 강의가 끝나는 시간과 다음 강의의 시작시간을 비교하여 만약 겹칠 경우 강의실을 하나 더 만들어주고 겹치지 않는다면 기존 강의실에 넣어준다.

 

 

# 1374 강의실

import sys, heapq
input = sys.stdin.readline


n = int(input())
lectures=[]
for _ in range(n):
    
    num, start, end = map(int, input().split())
    heapq.heappush(lectures, (start, end))


# 첫번째 강의가 끝나는 시간
heap=[]
end = heapq.heappop(lectures)[1]
heapq.heappush(heap,end)

cnt=1
for i in range(n-1):
    start2,end2 = heapq.heappop(lectures)
    end = heapq.heappop(heap)
    
    if start2 < end:
        # 강의 시간이 겹칠 경우
        heapq.heappush(heap, end)
        heapq.heappush(heap, end2)
        cnt+=1
    else:
        # 안겹치면 기존 강의실에 넣어
        heapq.heappush(heap, end2)
        
print(cnt)

우선 첫번째 강의가 끝나는 시간을 강의실 큐에 넣어놓고 두번째 강의부터 for문을 이용하여 판별하였다.

첫번 째 강의는 for문 이전에 pop한 상태이니

for문을 돌며 나오는 start2, end2는 두번째로 빨리 시작하는 강의가 될 것이다.

그리고 end는 첫번째 강의의 끝나는 시간이므로

첫번째 강의의 끝나는 시간(end)와 두번째 강의의 시작시간(start2)를 비교한다.

 

시간이 겹칠경우 강의실을 하나 더 만들어야 하기 때문에 pop했던 첫번째 강의 종료 시간을 넣고

두번째 강의 종료시간도 넣어준다. (따라서 종료 시간 개수가 강의실 수가 된다.)

 

시간이 겹치지 않는다면 기존 강의실에 넣어주면 되기 때문에 두번째 강의 종료 시간인 end2만 넣어준다.

 

복잡하지만 단순한 문제였다.