[BOJ/백준] 11000 강의실 배정

import heapq
import sys
input = sys.stdin.readline
N = int(input())

times = []
for _ in range(N):
    input_tuple = tuple(map(int,input().split()))
    heapq.heappush(times,input_tuple)

end_time_list = []
answer = 0
while times:
    start_time,end_time = heapq.heappop(times)
    if not end_time_list:
        answer += 1
        heapq.heappush(end_time_list,end_time)
    else:
        if end_time_list[0] > start_time:
            heapq.heappush(end_time_list,end_time)
            answer += 1
        else:
            heapq.heappop(end_time_list)
            heapq.heappush(end_time_list,end_time)
            
        
print(answer)

 

 

우선순위 힙을 응용한 문제이다. 먼저 (시작시간,종료시간)이 입력을 들어왔을때, 하나의 리스트에 저장을 해준다.

 

그리고 그것을 시작시간을 기준으로 정렬을 해준다.

 

그리고 하나씩 꺼내면서 판단을 해주면 된다.

 

end_time_list가 비워져있으면, 종료시간을 그냥 넣어준다.

 

end_time_list의 첫번째 값 즉. 가장 먼저 강의가 종료되는 시간보다, 현재 강의의 시작시간이 더 빠르면(작으면) 강의실을 여러개 구해야한다.

그러므로 answer를 +1 해주고, end_time_list에 현재 강의의 종료시간을 넣어준다.

 

그렇지 않을시에는, 강의실을 추가로 빌린필요가 없으므로, 가장 첫번째 값을 없애고, 현재 강의 종료시간을 end_time_list에 저장을 시켜준다.

 

end_time_list의 가장 첫번째 값은 가장 작은 값으로 유지되어야하므로, 우선순위 큐인 heapq를 사용했다.

 

 

 

import heapq
import sys
input = sys.stdin.readline

N = int(input())
class_list = []
for _ in range(N):
    start_time,end_time = map(int,input().split())
    class_list.append((start_time,end_time))

class_list.sort()
end_time_list = []
for start_time,end_time in class_list:
    if end_time_list:
        if end_time_list[0] <= start_time:
            heapq.heappop(end_time_list)
        heapq.heappush(end_time_list,end_time)
    else:
        heapq.heappush(end_time_list,end_time)

print(len(end_time_list))

좀 더 깔끔한 방식으로 푼 코드이다. 강의의 전체 정보를 저장하는 리스트는 굳이, 우선순위 힙을 쓸필요가 없으므로, 일반리스트로 쓰면서 정렬을 해줬다.

 

그리고 다른 변수로 answer를 저장하던걸 어차피, end_time_list의 길이와 답이 일치하므로, end_time_list의 길이로 답을 출력해주었다.