이 문제의 분류는 그리디 알고리즘과 우선순위 큐를 활용해서 푸는 문제입니다. 그리디 알고리즘만 사용하고 우선순위 큐를 사용하지 않는다면 시간초과가 나서 우선순위 큐를 사용하는 방법으로 구현해봤습니다.
k = int(s.readline())
#우선 순위 큐 저장 배열선언
heap =[]
#출력값들을 저장할 배열선언
answer= [0] * (k+1)
lecture = [list(map(int,s.readline().split())) for _ in range(k)]
#강의를 시작시간과 끝나는시간 기준으로 정렬
lecture.sort(key=lambda x:(x[1],x[2]))
강의를 시작시간과 끝나는시간으로 정렬하고 heap에 넣어야 새로운 강의를 넣을 때 마다 비교가 가능하므로 정렬해준다.
#1은 강의실번호
room_num=1
#끝나는 시간과 강의실 번호를 heap에 저장
hq.heappush(heap,[lecture[0][2],room_num])
#강의번호는 lecture배열의 첫번쨰 값
answer[lecture[0][0]] = room_num
강의실 번호를 세기위해 room_num이라는 변수를 생성해주고 강의 번호를 출력해줄 answer배열에 저장.
for i in range(1,k):
# 끝나는 시간보다 강의 시작시간이 작으면 heap에 push
if heap[0][0] > lecture[i][1]:
room_num +=1
answer[lecture[i][0]] = room_num
hq.heappush(heap,[lecture[i][2] ,room_num])
# 끝나는 시간보다 강의 시작시간이 크면 heappop하고 그 강의실번호를
# 새로 넣는 heap에 전달
else:
temp = hq.heappop(heap)
answer[lecture[i][0]] = temp[1]
hq.heappush(heap,[lecture[i][2],temp[1]])
k수만큼 반복하면서 끝나는 시간과 시작 시간을 비교하면서 끝나는 시간이 시작 시간보다 작은 값이 heap에 존재하면 pop해주고 push해주는 과정을 반복합니다. 이 과정을 하면서 빈 강의실을 사용해서 최대 강의실 번호를 유지할 수 있습니다.
전체코드
from sys import stdin as s
import heapq as hq
s=open("input.txt","rt")
k = int(s.readline())
#우선 순위 큐 저장 배열선언
heap =[]
#출력값들을 저장할 배열선언
answer= [0] * (k+1)
lecture = [list(map(int,s.readline().split())) for _ in range(k)]
#강의를 시작시간과 끝나는시간 기준으로 정렬
lecture.sort(key=lambda x:(x[1],x[2]))
#1은 강의실번호
room_num=1
#끝나는 시간과 강의실 번호를 heap에 저장
hq.heappush(heap,[lecture[0][2],room_num])
#강의번호는 lecture배열의 첫번쨰 값
answer[lecture[0][0]] = room_num
for i in range(1,k):
# 끝나는 시간보다 강의 시작시간이 작으면 heap에 push
if heap[0][0] > lecture[i][1]:
room_num +=1
answer[lecture[i][0]] = room_num
hq.heappush(heap,[lecture[i][2] ,room_num])
# 끝나는 시간보다 강의 시작시간이 크면 heappop하고 그 강의실번호를
# 새로 넣는 heap에 전달
else:
temp = hq.heappop(heap)
answer[lecture[i][0]] = temp[1]
hq.heappush(heap,[lecture[i][2],temp[1]])
print(len(heap))
for i in range(1,len(answer)):
print(answer[i])
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 14502 연구소 [Python] (0) | 2023.05.11 |
---|---|
[백준] 14503 로봇 청소기 [Python] (0) | 2023.05.10 |
[백준] 1520 내리막길 [Python] (0) | 2023.05.05 |
[백준] 11660 구간 합 구하기 5 [Python] (0) | 2023.05.05 |
[백준] 18405 경쟁적 전염[Python] (0) | 2023.04.27 |