사용 언어 - Python3
문제 - 운영체제
https://school.programmers.co.kr/learn/courses/15008/lessons/121686
정답
heapq 우선순위 큐
모든 부모들로 거슬러 올라가서 그 부모가 몇 번째 자식이었는지 확인
import heapq
heap = [] 우선순위 큐를 통해 프로그램 대기 list를 만들어준다.
0. time = 0 에서 시작
1. 호출시간과 우선순위를 기준으로 정렬한다.
빨리 호출된 순서대로, 호출시간이 같다면 우선순위가 높은 순으로 1차 정렬한다.
program.sort(key = lambda x: (x[1],x[0]))
2. 시간을 기준으로 push & pop
현재 시간 기준, 아직 호출되지 않았다면 그 값을 heapq에 push하고 program엔 pop해주며 빨리 처리해야하는 순서대로 heapq에 저장해준다.
더이상 현 시간에서는 대기시킬 프로그램이 없다면, 시간을 프로그램의 실행시간으로 늘려주면서 위 push, pop을 반복한다.
3. 우선순위대로 대기시간 계산
우선순위대로 저장된 heapq를 한개씩 pop하면서 한 프로그램씩 대기시간을 계산해준다.
대기시간 = 현재시간 - 호출시간
answer[프로그램점수] += 대기시간
한 프로그램 끝날 때마다 time += 실행시간
4. answer[0] = 프로그램 종료 시간 = 마지막 time
import heapq
def solution(program):
answer = [0] * 11
heap = [] # 우선순위 큐. 프로그램 대기 list
program.sort(key=lambda x: (x[1], x[0])) # 호출시간+우선순위 정렬
time = 0
while program or heap:
# 아직 호출되지 않았다면 (=호출시간이 현재 시간보다 작다면)
# 그 값을 heap에 push하고 pop해준다.
while program and program[0][1] <= time:
heapq.heappush(heap, program.pop(0))
# 대기시킬 프로그램이 없는 경우,
# 현재시간을 호출시간으로 바꾸기
if program and not heap:
time = program[0][1]
heapq.heappush(heap, program.pop(0))
# 우선순위대로 실행
temp = heapq.heappop(heap)
# 대기시간 = 현재시간-호출시간
# 현재시간 += 실행시간
answer[temp[0]] += (time - temp[1])
time += temp[2]
answer[0] = time
return answer
(내 오답)
테스트케이스만 통과하는 풀이였다...
heapq 말고 q를 사용했음
from collections import deque
def solution(program):
answer = [0]*11
# 빨리 도착한 순으로 정렬
program.sort(key = lambda x:x[1])
# 늦게 도착했지만 점수가 더 낮다면 두개 자리 바꿔주기
for i in range(1,len(program)-1):
if program[i+1][0] < program[i][0]:
program[i], program[i+1] = program[i+1], program[i]
q = deque() # 끝시간 기록
q.append(program[0][1] + program[0][2]) # 첫 프로그램의 끝시간 = 시작시간+실행시간
for i in range(1,len(program)):
# 두번째 프로그램의 시작시간 = 첫번째 프로그램의 끝시간
# 2번째의 대기시간 = 두번째 프로그램의 시작시간 - 도착시간
now = q.popleft()
# 두번째 프로그램의 끝시간 = 세번째 프로그램의 시작시간 = 첫번째 프로그램의 끝시간+실행시간
q.append(now + program[i][2])
# 프로그램 점수가 i인 프로그램들의 대기시간의 합
for j in range(1,11): # 프로그램 점수 종류 최대 10개
if j == program[i][0]: # 프로그램 점수에 해당한다면
answer[j] += now - program[i][1]
# 끝나는 시간
answer[0] = now + program[i][2]
return answer
레퍼런스
'Algorithm > 스택&큐&덱&힙' 카테고리의 다른 글
[프로그래머스] PCCP 모의고사 2회 3번 카페 확장 (1) | 2023.12.15 |
---|---|
[프로그래머스] PCCP 모의고사 2회 2번 신입사원 교육 (0) | 2023.12.15 |
[프로그래머스] PCCP 모의고사 1회 3번 유전법칙 (0) | 2023.12.14 |
[프로그래머스 lv 3] 이중우선순위큐 (0) | 2023.06.19 |
[프로그래머스 lv 3] 디스크 컨트롤러 (0) | 2023.06.19 |
댓글