[PCCP 모의고사 #1_04] 운영체제

문제

https://school.programmers.co.kr/learn/courses/14760/lessons/125486

풀이

priority queue와 heapq를 각각 사용하여 알고리즘을 구현하였다.

• priority queue는 한 번 실행할 때마다 thread safety 과정을 진행하고, heapq는 진행하지 않기 때문에 heapq의 실행 속도가 priority queue 보다 더 빠르다.
• 따라서 heapq를 사용한 코드가 미세하게 실행 속도가 더 빠른 결과를 나타내었다.

코드

• 꼭 다시 풀어볼 것!

정답 (Priority Queue 사용)

from queue import PriorityQueue
def solution(program):
    answer = [0]*11         # 프로그램 우선순위는 1~10번까지 존재하므로 (answer[0]은 최종 실행 시간)
    program.sort(key = lambda x : x[1])
    pQ = PriorityQueue()
    cur = 0         # 현재 시각
    
    def call_program():     # program 배열 안의 프로그램을 pQ에 넣어주는 작업
        while len(program) > 0 and program[0][1] <= cur:
            pQ.put(program.pop(0))
    cur = 0
    while len(program) > 0 or not pQ.empty():
        if pQ.empty():      # pQ가 비어있다면
            cur = program[0][1]        # program 배열의 맨 앞의 값의 시각을 현재 시각으로 설정
            call_program()
        execute = pQ.get()      # 가장 앞의 값을 제거
        answer[execute[0]] += (cur - execute[1])      # answer 배열의 해당 우선순위 인덱스에 대기 시간 값을 추가함
        cur += execute[2]       # 현재 시각을 갱신
        call_program()
    
    answer[0] += cur        # answer[0]은 모든 프로그램이 종료되는 시각
    
    return answer

실행 결과

• 모든 테스트 케이스에 대해 통과되었지만, 처리 속도가 늦은 경우들이 있어 시간복잡도를 개선하는 방안을 생각해보고자 한다.

정답 (heapq 사용)

import heapq

def solution(program):
    answer = [0]*11         # 프로그램 우선순위는 1~10번까지 존재하므로 (answer[0]은 최종 실행 시간)
    program.sort(key = lambda x : x[1])
    heap = []         # heapq의 경우 리스트를 사용해야 함
    cur = 0         # 현재 시각
    
    def call_program():     # program 배열 안의 프로그램을 pQ에 넣어주는 작업
        while len(program) > 0 and program[0][1] <= cur:
            heapq.heappush(heap, program.pop(0))
    cur = 0
    while len(program) > 0 or not len(heap) == 0:
        if len(heap) == 0:      # pQ가 비어있다면
            cur = program[0][1]        # program 배열의 맨 앞의 값의 시각을 현재 시각으로 설정
            call_program()
        execute = heapq.heappop(heap)      # 가장 앞의 값을 제거
        answer[execute[0]] += (cur - execute[1])      # answer 배열의 해당 우선순위 인덱스에 대기 시간 값을 추가함
        cur += execute[2]       # 현재 시각을 갱신
        call_program()
    
    answer[0] += cur        # answer[0]은 모든 프로그램이 종료되는 시각
    
    return answer

실행 결과

• priority queue를 사용했을 때보다 시간복잡도를 개선하였다.