[BOJ/백준] 21773 가희와 프로세스 1

import heapq
import sys
input = sys.stdin.readline
 
T,N = map(int,input().split())
 
heap_list = []
 
 
for _ in range(N):
    id_num,times,C = map(int,input().split())
    heapq.heappush(heap_list,(-C,id_num,times))
 
result = []
for _ in range(T):
 
    prioty,id_num,times = heapq.heappop(heap_list)
    times -= 1
    result.append(id_num)
    if times != 0:
        heapq.heappush(heap_list,(prioty+1,id_num,times))
 
 
for i in range(T):
    sys.stdout.write(str(result[i])+'\n')

시간초과에 많이 힘들었던 문제였다. 문제를 푸는 로직은 맞지만, 출력을 하는데 시간이 오래 걸리는것 같다.

 

이 문제의 주어진 조건은 한 타임에 실행된 프로세스를 제외한, 나머지 프로세스들의 우선순위가 전부 1이 증가한다.

 

 

이 말의 뜻은 자기만 우선순위가 1이 줄어드는것과 같다.

 

그러므로 이 문제는 heapq를 이용해서 1순위로 priority가 가장 높은게 가장 앞으로 오게, 그 다음은 id가 가장 작은게 오도록 넣어준다.

 

그리고 하나씩 꺼내면서 시간을 줄여주고, 우선순위도 줄여주는데 max_heapq를 해야하므로, 여기서는 +1을 해주었다.

 

만약 시간이 0 이면 그 프로세스는 실행이 안되므로, push를 해주지 않았다.