[프로그래머스] PCCP 모의고사 1회 4번 운영체제

사용 언어 - 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

 

 

 

 

 

레퍼런스