[Programmers/Python] 운영체제

프로그래머스

프로그래머스 파이썬 PCCP 모의고사 1회 4번 운영체제 121686

문제 설명

개발자 준모는 운영체제를 만들었습니다. 준모가 만든 운영체제는 프로그램의 우선순위와 호출된 시각에 따라 실행 순서를 결정합니다. 모든 프로그램에는 1부터 10까지의 점수가 매겨져 있으며, 이 점수가 낮을수록 우선순위가 높은 프로그램입니다. 각 프로그램들은 실행 시간이 정해져 있으며 프로그램이 호출되면 대기상태에 있다가 자신의 순서가 되면 실행 시간 동안 실행된 뒤 종료됩니다.

준모가 만든 운영체제는 호출된 프로그램들 중 우선순위가 가장 높은 프로그램을 먼저 실행합니다. 호출된 각 프로그램은 자신보다 우선순위가 높은 호출된 프로그램이 모두 종료된 후에 실행됩니다. 단, 실행 중인 프로그램보다 우선순위가 높은 프로그램이 호출되어도 실행 중이던 프로그램은 중단되지 않고 종료될 때까지 계속 실행됩니다. 또한, 우선순위가 같은 프로그램들 중에서는 먼저 호출된 프로그램이 먼저 실행됩니다.

다음은 1번부터 4번까지의 4개의 프로그램이 호출된 예시입니다.

예를 들어, 1번부터 4번까지 4개의 프로그램의 점수가 순서대로 2, 1, 3, 3이며, 호출된 시각은 0, 5, 5, 12초이고, 수행시간은 10, 5, 3, 2라고 가정해 봅시다.

1. 1번 프로그램이 0초에 호출될 때 실행 중인 프로그램이 없으므로, 0초에 1번 프로그램이 바로 실행됩니다. 1번 프로그램은 10초에 종료되며, 2, 3번 프로그램이 새로 호출됐습니다.
2. 호출된 2, 3번 프로그램 중 2번 프로그램의 점수가 1로 우선순위가 높습니다. 2번 프로그램은 5초에 호출되어 10초에 실행될 때까지 5초 동안 대기했습니다. 2번 프로그램은 15초에 종료되며, 4번 프로그램이 새로 호출됐습니다.
3. 호출된 3, 4번 프로그램은 점수가 같지만, 3번 프로그램이 먼저 호출되었기 때문에 3번 프로그램이 먼저 실행됩니다. 3번 프로그램은 5초에 호출되어 15초에 실행될 때까지 10초 동안 대기했습니다. 3번 프로그램은 18초에 종료됩니다.
4. 4번 프로그램이 마지막으로 실행되며, 4번 프로그램은 12초에 호출되어 18초에 실행될 때까지 6초 동안 대기했습니다. 4번 프로그램은 20초에 종료됩니다.

모든 프로그램이 종료되는 시각은 20초이며, 각 프로그램이 대기한 시간은 순서대로 0, 5, 10, 6초입니다. 점수가 1인 프로그램의 대기시간 합은 5고, 점수가 3인 프로그램의 대기시간 합은 16 임을 알 수 있습니다.

프로그램들의 정보를 나타내는 2차원 정수 배열 program이 주어질 때, 모든 프로그램들이 종료되는 시각과 프로그램의 점수마다 대기시간의 합을 정수 배열에 담아 return 하는 solution 함수를 완성하세요. return 해야 하는 answer 배열은 길이가 11인 정수 배열입니다. answer[0]은 모든 프로그램들이 종료되는 시각을 의미하며, answer[i](1 ≤ i ≤ 10)는 프로그램의 점수가 i인 프로그램들의 대기시간의 합을 의미합니다.

---

제한사항

• 1 ≤ program의 길이 ≤ 100,000
• program[i]은 i+1번 프로그램의 정보를 의미하며, [a, b, c]의 형태로 주어집니다.
  • a는 프로그램의 점수를 의미하며, 1 ≤ a ≤ 10 을 만족합니다.
  • b는 프로그램이 호출된 시각을 의미하며, 0 ≤ b ≤ 10,000,000을 만족합니다.
  • c는 프로그램의 실행 시간을 의미하며, 1 ≤ c ≤ 1,000을 만족합니다.
  • a, b쌍이 중복되는 프로그램은 입력으로 주어지지 않습니다. 즉, 호출된 시각이 같으면서 점수도 같은 프로그램은 없습니다.

📌 문제 풀이

1. 먼저, 호출 시각에 따라 정렬해주는 것이 좋다. 호출 시각이 동일하다면, 점수가 낮은 것이 앞으로 오도록 정렬해준다.
2. 호출 시각을 현재 시간과 비교하여, 대기 중인 프로그램을 구해준다.
3. 이를 우선순위 큐에 넣어준 후, 점수가 낮아 우선순위가 높은 프로그램을 실행해주도록 한다.
2번과 3번을 반복하여, 대기 중이여야 하는 프로그램을 큐에 넣어주고, 우선순위가 가장 높은 프로그램을 실행하도록 한다.
 

import heapq

def solution(programs):
    programs.sort(key = lambda x : (x[1], x[0]))
    time = 0
    idx = 0
    waiting = []
    program = []    
    answer = [0 for _ in range(10)]
    ...

파이썬에서 PriorityQueue를 이용하는 방법과, heapq를 이용하는 방식이 있는데, heapq을 이용하여 풀었다.
우선순위 큐를 이용해주지 않고 코드를 짜다가,,, 도저히 안될 것 같아서 heapq을 이용해주게 되었다.
sort를 통해서 x[1] (호출 시각), x[0] (점수) 순으로 정렬을 해주었다. 

• time : 현재 시간
• idx : 프로그램 리스트에서의 인덱스 표현
• waiting : 우선순위 큐로 대기 중인 프로그램이 담긴다.
• program : 프로그램
• answer : 점수별 대기 시간 합이 들어갈 리스트

 

    while idx < len(programs):    
        for i in range(idx, len(programs)):
            if programs[idx][1] <= time:
                heapq.heappush(waiting, programs[idx])
                idx += 1
            else:
                break
        if len(waiting) != 0:
            program = heapq.heappop(waiting)
            answer[program[0] - 1] += time - program[1]
            time += program[2]
        else:
            time += 1
            
       ...

programs를 for문을 통해 각 프로그램의 호출 시각과 현재 시간을 비교하여 우선순위 큐에 담아준다.
모든 program이 우선순위 큐에 담겨지게 되어 idx가 프로그램 리스트 길이보다 커진다면, 반복문은 종료된다.
대기 중인 프로그램 리스트인 waiting, 우선순위 큐에 남아있는 프로그램이 있다면, 가장 우선순위가 높은 프로그램의 실행시간만큼 현재시간을 갱신해준다. 
점수별 대기 시간 합을 위해 현재 시간 - 호출 시각을 저장해준다.
만약, 아무것도 대기시킬 프로그램이 없는 경우 즉, 현재 시간은 15초인데 남은 프로그램들의 호출 시각은 모두 16초 이상이라면, time을 1씩 증가시킨다. (1씩 증가시키면 시간이 많이 걸려서 뒷부분엔 다른 방식으로 바꿔주었다.)
또한, for문에서 else: break를 해주어야 시간 초과를 방지할 수 있었다. 
 
이렇게 idx가 프로그램 리스트 길이보다 커진 순간 반복문이 종료된다면,
아직 우선순위 큐에 남아있는 프로그램들이 있을 수 있다.

    while len(waiting) > 0:
        program = heapq.heappop(waiting)
        answer[program[0] - 1] += 0 if time - program[1] < 0 else time - program[1]
        time += program[2]

    return [time] + answer

따라서, 남아있는 프로그램이 없을 때까지 pop해가며 시간을 반영한다.
 

✅ [ CODE ]

import heapq

def solution(programs):
    time = 0
    programs.sort(key = lambda x : (x[1], x[0]))
    idx = 0
    waiting = []
    answer = [0 for _ in range(10)]
    program = []    
    
    while idx < len(programs):    
        for i in range(idx, len(programs)):
            if programs[idx][1] <= time:
                heapq.heappush(waiting, programs[idx])
                idx += 1
            else:
                break
        if len(waiting) != 0:
            program = heapq.heappop(waiting)
            answer[program[0] - 1] += time - program[1]
            time += program[2]
        else:
            time += 1
    
    while len(waiting) > 0:
        program = heapq.heappop(waiting)
        answer[program[0] - 1] += 0 if time - program[1] < 0 else time - program[1]
        time += program[2]

    return [time] + answer

 
코드가 중복되기 때문에, while문의 조건을 추가해주어 남은 우선순위 큐를 모두 털어버리는 마지막 while문을 삭제할 수 있었다.

✅ [ CODE ]

import heapq

def solution(programs):
    time = 0
    programs.sort(key = lambda x : (x[1], x[0]))
    idx = 0
    waiting = []
    answer = [0 for _ in range(10)]
    program = []    
    
    while idx < len(programs) or len(waiting) != 0:    
        for i in range(idx, len(programs)):
            if programs[idx][1] <= time:
                heapq.heappush(waiting, programs[idx])
                idx += 1
            else:
                break
        if len(waiting) != 0:
            program = heapq.heappop(waiting)
            answer[program[0] - 1] += time - program[1]
            time += program[2]
        else:
            time += 1
            
    return [time] + answer

 
또한 시간을 1초씩 흐르게 할 필요없이 바로 idx에 해당하는 프로그램 호출 시각으로 time을 변동해준다면, 실행 시간을 더 축소시킬 수 있다. te__ho 코드 매우 감사

✅ [ CODE ]

import heapq
 
def solution(programs):
    time = 0
    programs.sort(key = lambda x : (x[1], x[0]))
    idx = 0
    waiting = []
    answer = [0 for _ in range(10)]
    program = []    
    
    while idx < len(programs) or len(waiting) != 0:
        
        if len(waiting) == 0:
            time = programs[idx][1]
            # for i in range(idx, len(programs)):
            #     if programs[idx][1] <= time:
            #         heapq.heappush(waiting, programs[idx])
            #         idx += 1
            #     else:
            #         break
            while idx != len(programs) and programs[idx][1] <= time:
                heapq.heappush(waiting, programs[idx])
                idx += 1
                    
        program = heapq.heappop(waiting)
        answer[program[0] - 1] += time - program[1]
        time += program[2]
        
        # for i in range(idx, len(programs)):
        #     if programs[idx][1] <= time:
        #         heapq.heappush(waiting, programs[idx])
        #         idx += 1
        #     else:
        #         break
        while idx != len(programs) and programs[idx][1] <= time:
            heapq.heappush(waiting, programs[idx])
            idx += 1
            
    return [time] + answer

while이 더 실행 시간이 짧게 나오긴 했다.
 

✅ [ CODE ]

중복되는 부분을 함수로 묶어주었다.

import heapq

 
def solution(programs):
    time = 0
    programs.sort(key = lambda x : (x[1], x[0]))
    global idx
    idx = 0
    waiting = []
    answer = [0 for _ in range(10)]
    program = []    
    
    def push():
        global idx
        while idx != len(programs) and programs[idx][1] <= time:
            heapq.heappush(waiting, programs[idx])
            idx += 1
    
    while idx < len(programs) or len(waiting) != 0:
        
        if len(waiting) == 0:
            time = programs[idx][1]
            push()
                    
        program = heapq.heappop(waiting)
        answer[program[0] - 1] += time - program[1]
        time += program[2]
        
        push()
            
    return [time] + answer