21773. 가희와 프로세스

문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 보러 가기

접근 과정

1초마다 수행시킬 스케쥴러를 선택해야 하는데, 최우선 고려 사항은 우선 순위 값이 제일 커야 하고, 우선 순위 값이 동일한 프로세스가 여러 개 있다면 그 중에서 id값이 가장 작은 프로세스를 선택해야 한다.

먼저 들어오는 데이터가 먼저 나가는 구조가 아니라, 매 순간마다 들어온 순서와는 무관하게 특정한 기준에 따라 정해지는 우선 순위가 높은 데이터가 나와야 한다는 점에서 우선 순위 큐를 사용해야겠다는 생각을 할 수 있었다.

첫 풀이

우선 순위 큐를 사용해야겠다고 생각했기 때문에, heapq 모듈을 사용해 구현하기로 하였다.

import heapq
import sys

class Data:
    def __init__(self, id, time, priority):
        self.id = id
        self.time = time
        self.priority = priority
    
    def __lt__(self, other):
        if self.priority == other.priority:
            return self.id < other.id
        else:
            return self.priority > other.priority 

  
input = sys.stdin.readline
N, M = map(int, input().split())
time_count = N
hq = []

for _ in range(M):
    id, time, priority = map(int, input().split())
    heapq.heappush(hq, Data(id, time, priority))    

while time_count:
    element = heapq.heappop(hq)
    hq_size = len(hq)
    another_hq = []
    print(element.id)
    for _ in range(hq_size):
        not_chosen_element = heapq.heappop(hq)
        heapq.heappush(another_hq, Data(not_chosen_element.id, not_chosen_element.time, not_chosen_element.priority + 1))
    if element.time - 1:
        heapq.heappush(another_hq, Data(element.id, element.time - 1, element.priority))
    hq = another_hq
    time_count -= 1

프로세스들을 우선 순위 큐에 넣고, 주어진 시간 T초 동안 우선 순위 큐에서 실행할 프로세스를 하나 뽑아온다.

1초가 지나면 실행되지 않은 나머지 프로세스들의 우선 순위가 1 상승한다는 조건이 있었기 때문에, 새로운 우선 순위 큐를 만들어 기존 우선 순위 큐의 나머지 프로세스들을 우선 순위 값만 1씩 증가시켜 다시 삽입하고, 실행한 프로세스를 넣은 뒤 우선 순위 큐를 바꾸어주는 식으로 진행하였지만... 시간 초과가 발생하였다.

테스트 케이스들에 대한 출력도 문제가 없는 것처럼 보였지만, "선택되지 않은 프로세스의 우선 순위를 1 상승"시키는 과정을 구현하기 위해 주어진 시간 T만큼 기존의 우선 순위 큐에서 요소들을 전부 가져와 새로운 우선 순위 큐에 요소를 전부 삽입한 과정이 시간 초과의 원인이 되었다.

heapq 모듈에서 사용하는 heappush() 함수와 heappop() 함수는 O(log N)의 시간 복잡도를 가지지만, 주어진 데이터 T와 n의 최댓값(1000000, 100000)을 고려했을 때 1000000초동안 100000개의 프로세스들에 대해 이러한 방식의 연산을 수행해 결국 시간 초과가 발생한 것 같다.

선택되지 않은 프로세스의 우선 순위 값을 어떻게 바꾸어줄지 고민하게 되었는데, 생각해보니 꼭 우선 순위 값을 올려서 저장할 필요가 없었다.

선택되지 않은 프로세스의 값을 1 올리는 것이 아니라, 선택되어 1초 동안 실행된 프로세스의 우선 순위 값을 1 내려서 삽입하는 것으로도 우선 순위가 가장 높은 프로세스가 선택되게 하는 로직에는 문제가 없었기 때문이다!

수정한 풀이

import sys
import heapq

class Data:
    def __init__(self, p_id, time, priority):
        self.p_id = p_id
        self.time = time
        self.priority = priority
    
    def __lt__(self, other):
        if self.priority == other.priority:
            return self.p_id < other.p_id
        else:
            return self.priority > other.priority 

        
input = sys.stdin.readline
N, M = map(int, input().split())
time_count = N
hq = []

for _ in range(M):
    p_id, time, priority = map(int, input().split())
    heapq.heappush(hq, Data(p_id, time, priority))    

while time_count:
    element = heapq.heappop(hq)
    print(element.p_id)
    if element.time - 1:
        heapq.heappush(hq, Data(element.p_id, element.time - 1, element.priority - 1))
    
    time_count -= 1

통과!

읽어주셔서 감사합니다!