문제 설명
•
주어진 프로그램들을 우선순위와 호출 시각에 따라 실행하고, 각 프로그램의 종료 시점과 프로그램 점수별 대기시간 합을 구하는 문제
예제 입력/출력
program | result(answer) |
[[2, 0, 10], [1, 5, 5], [3, 5, 3], [3, 12, 2]] | [20, 5, 0, 16, 0, 0, 0, 0, 0, 0, 0] |
[[3, 6, 4], [4, 2, 5], [1, 0, 5], [5, 0, 5]] | [19, 0, 0, 4, 3, 14, 0, 0, 0, 0, 0] |
제약 조건
•
program의 길이
•
program[i] 은 [a, b, c]의 형태
◦
: 프로그램의 점수
◦
: 프로그램이 호출된 시각
◦
: 프로그램의 실행 시간
◦
쌍이 중복되는 프로그램은 입력으로 주어지지 않는다.
문제 풀이
접근1 우선순위 큐를 활용한 시뮬레이션 -
풀이 코드
•
접근1 우선순위 큐를 활용한 시뮬레이션 -
import heapq
def solution(program):
answer = [0 for _ in range(10)]
program.sort(key=lambda x: x[1])
memory = []
cur_time = 0
# 프로그램이 아직 남아 있거나 메모리에 실행 대기 중인 프로그램이 있으면 계속 반복
while program or memory:
# 현재 실행할 프로그램이 없을 때 시간을 건너뜀
if not memory:
cur_time = program[0][1]
else:
# 메모리에서 우선순위가 가장 높은 프로그램을 꺼냄
process = heapq.heappop(memory)
# 프로그램이 대기했던 시간 = 현재 시간 - 호출된 시간
answer[process[0] - 1] += cur_time - process[1]
# 실행 시간만큼 현재 시간을 업데이트
cur_time += process[2]
# 호출해야 할 프로그램을 메모리에 적재
while program and program[0][1] <= cur_time:
heapq.heappush(memory, program.pop(0))
return [cur_time, *answer]
Python
복사
