[PCCP 모의고사#1] 운영체제 (우선순위큐)

문제 설명

개발자 준모는 운영체제를 만들었습니다. 준모가 만든 운영체제는 프로그램의 우선순위와 호출된 시각에 따라 실행 순서를 결정합니다. 모든 프로그램에는 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쌍이 중복되는 프로그램은 입력으로 주어지지 않습니다. 즉, 호출된 시각이 같으면서 점수도 같은 프로그램은 없습니다.

입출력 예

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]

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 그림으로 나타내면 아래 그림과 같습니다.

풀이

• 우선순위 나오니까 우선순위 큐다.
• 아는 거 나오면 갑자기 무지성 코더로 변신 ㅡ.ㅡ;;; 
• 땡~ ㅋㅋㅋ

from queue import PriorityQueue

def solution(program):
    answer = [0 for _ in range(11)]
    ctime = 0 # 누적 실행 시간
    cjob = -1 # 현재 작업 인덱스 (-1은 비어있음)

    cq = PriorityQueue() # 호출 시각 순으로 작업저장
    
    for i,p in enumerate(program):
        cq.put((p[1],p[0],p[2])) # 호출시각, 우선순위, 실행시간, 인덱스
    
    while cq.empty() != True:
        호출시간, 우선순위, 실행시간 = cq.get()
        if ctime > 호출시간:
            answer[우선순위] += ctime - 호출시간
        ctime += 실행시간
    
    answer[0] = ctime
    
    print(program)
    print(answer)
    return answer

테스트 1
입력값 〉	[[2, 0, 10], [1, 5, 5], [3, 5, 3], [3, 12, 2]]
기댓값 〉	[20, 5, 0, 16, 0, 0, 0, 0, 0, 0, 0]
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	
[[2, 0, 10], [1, 5, 5], [3, 5, 3], [3, 12, 2]]
[20, 5, 0, 16, 0, 0, 0, 0, 0, 0, 0]

테스트 2
입력값 〉	[[3, 6, 4], [4, 2, 5], [1, 0, 5], [5, 0, 5]]
기댓값 〉	[19, 0, 0, 4, 3, 14, 0, 0, 0, 0, 0]
실행 결과 〉	
실행한 결괏값 [19,0,0,9,8,5,0,0,0,0,0]이 기댓값 [19,0,0,4,3,14,0,0,0,0,0]과 다릅니다.
출력 〉	
[[3, 6, 4], [4, 2, 5], [1, 0, 5], [5, 0, 5]]
[19, 0, 0, 9, 8, 5, 0, 0, 0, 0, 0]

• 그래... 이렇게 쉬울리 없어... 4번째 문제잖아... ㅜ.ㅡ;
• 고쳐봤더니 이번엔 첫번째 거 통과 못 함

from queue import PriorityQueue

def solution(program):
    answer = [0 for _ in range(11)]
    ctime = 0 # 누적 실행 시간
    cjob = -1 # 현재 작업 인덱스 (-1은 비어있음)

    cq = PriorityQueue() # 호출 시각 순으로 작업저장
    
    for i,p in enumerate(program):
        cq.put((p[1],p[0],p[2],i)) # 호출시각, 우선순위, 실행시간, 인덱스
    
    while cq.empty() != True:
        호출시간, 우선순위, 실행시간,i = cq.get()
        if ctime > 호출시간: # 이미 시간이 지나갔음
            # 대기열로 다시 집어넣기
            cq.put((ctime, 우선순위, 실행시간,i))
        else:
            answer[우선순위] = ctime - program[i][1] # 기다린 시간
            ctime += 실행시간
    
    answer[0] = ctime
    
    return answer

테스트 1
입력값 〉	[[2, 0, 10], [1, 5, 5], [3, 5, 3], [3, 12, 2]]
기댓값 〉	[20, 5, 0, 16, 0, 0, 0, 0, 0, 0, 0]
실행 결과 〉	
실행한 결괏값 [20,5,0,12,0,0,0,0,0,0,0]이 기댓값 [20,5,0,16,0,0,0,0,0,0,0]과 다릅니다.

테스트 2
입력값 〉	[[3, 6, 4], [4, 2, 5], [1, 0, 5], [5, 0, 5]]
기댓값 〉	[19, 0, 0, 4, 3, 14, 0, 0, 0, 0, 0]
실행 결과 〉	테스트를 통과하였습니다.

• 미치겠네 ㅋㅋㅋ
  • 이거 쉬운 거 같으면서 어렵다. 다시...
• 다시 첨부터 정리
  • 먼저 작업을 호출순으로 우선순위 큐에 넣는다.
  • 첫번째 작업
    • 프로세스가 비어있으면, 호출큐에서 꺼낸 첫번째 작업을 바로 실행하고 누적 시간 갱신
  • 두번째 작업은 누적시간이 갱신되어 있으므로 큐에서 꺼내기 전에 현재 시간과 호출 시각의 비교 
    • 누적시간이 호출시간보다 작다? 그럼 작업 실행
    • 누적시간이 호출시간보다 크다? 그럼 일단 작업큐에 넣고 하나 더 꺼냄
      • 하나 더 꺼낸 작업의 호출시간이 누적시간보다 작으면 또 꺼냄...
  • 작업큐에 넣은 작업은 우선순위가 작은 것부터 꺼내서 작업 실행
    • 누적 시간 갱신.
      • 호출큐에서 하나 꺼내서 누적시간보다 호출시간이 작으면 작업큐에 넣기
      • 그리고 계속 반복. 호출시간 보다 큰 작업이 나올 때 까지 반복
  • 그 담에 작업 하다가
    • 작업큐도 비었고, 호출큐에서 꺼낸 것도 누적시간보다 호출시간이 크면.
    • 작업 종료. 프로세스는 비어있고, 맨앞으로 가서
  • 작업큐가 비어있으니 호출큐에서 꺼낸 것 실행하고 누적 시간 갱신
• 까지 생각하고 코드를 짜보았으나......... 망!
  • PCCP 쉽지 않다. 좀 더 공부하고 시험을 치든 해야할 것 같다.

from heapq import heapify as heapify, heappush as push, heappop as pop

def solution(program):
    answer = [0 for _ in range(11)]
    ctime = 0 # 누적 실행 시간

    waitq = [] # 호출 시각 순으로 작업저장
    taskq = [] # 우선 순위 순으로 작업저장
    
    for i,p in enumerate(program):
        push(waitq, (p[1],p[0],p[2])) # [0]우선순위, [1]호출시각, [2]실행시간, [i]인덱스
    
    호출시각, 우선순위, 실행시간 = pop(waitq) # 대기 큐에서 꺼내서
    ctime = 호출시각 # 시간을 갱신하고
    push(taskq, (우선순위,호출시각,실행시간)) # 작업 큐에 밀어넣기
    
    while len(taskq) >0 or len(waitq) > 0:
        
        if len(taskq) == 0: # 작업이 비었을 때 시간을 호출시간으로 변경하고 작업큐로 옮기기
            ctime = waitq[0][0]
            while len(waitq) > 0 and waitq[0][0] <= ctime: # 작업 큐에 밀어넣기
                호출시각, 우선순위, 실행시간 = pop(waitq)
                push(taskq, (우선순위,호출시각,실행시간))
        
        우선순위, 호출시각, 실행시간 = pop(taskq) # 작업 큐에서 꺼내서
        answer[우선순위] += ctime - 호출시각 # 우선순위 배열에 대기시간을 입력함
        ctime += 실행시간 # 누적 시간 갱신
        
        while len(waitq) > 0 and waitq[0][0] <= ctime: # 시간이 갱신 됐으니까 지나간게 있으면 작업 큐로 옮긴다.
            호출시각, 우선순위, 실행시간 = pop(waitq)
            push(taskq, (우선순위,호출시각,실행시간))
            
    answer[0] = ctime
    
    return answer

정확성  테스트
테스트 1 〉	통과 (2.13ms, 10.7MB)
테스트 2 〉	통과 (132.63ms, 21.5MB)
테스트 3 〉	통과 (87.54ms, 16.1MB)
테스트 4 〉	통과 (68.40ms, 16.8MB)
테스트 5 〉	통과 (149.43ms, 22.3MB)
테스트 6 〉	통과 (288.01ms, 31.5MB)
테스트 7 〉	통과 (7.96ms, 11.4MB)
테스트 8 〉	통과 (104.60ms, 19.7MB)
테스트 9 〉	통과 (89.96ms, 17.6MB)
테스트 10 〉	통과 (305.83ms, 33.2MB)
테스트 11 〉	통과 (307.52ms, 33.1MB)
테스트 12 〉	통과 (294.58ms, 33.1MB)
테스트 13 〉	통과 (402.38ms, 33.3MB)
테스트 14 〉	통과 (421.53ms, 33.2MB)

• 약간의 차이. 별로 의미는 없다. ㅎㅎ

from heapq import heapify as heapify, heappush as push, heappop as pop

def solution(program):
    answer = [0 for _ in range(11)]
    ctime = 0 # 누적 실행 시간

    waitq = [] # 호출 시각 순으로 작업저장
    taskq = [] # 우선 순위 순으로 작업저장
    
    for i,p in enumerate(program):
        push(waitq, (p[1],p[0],p[2])) # [0]우선순위, [1]호출시각, [2]실행시간, [i]인덱스
    
    호출시각, 우선순위, 실행시간 = pop(waitq) # 대기 큐에서 꺼내서
    ctime = 호출시각 # 시간을 갱신하고
    push(taskq, (우선순위,호출시각,실행시간)) # 작업 큐에 밀어넣기
    
    while len(taskq) >0 or len(waitq) > 0:
        
        if len(taskq) == 0: # 작업이 비었을 때 시간을 호출시간으로 변경하고 작업큐로 옮기기
            ctime = waitq[0][0]
            호출시각, 우선순위, 실행시간 = pop(waitq)
            push(taskq, (우선순위,호출시각,실행시간))
        
        우선순위, 호출시각, 실행시간 = pop(taskq) # 작업 큐에서 꺼내서
        answer[우선순위] += ctime - 호출시각 # 우선순위 배열에 대기시간을 입력함
        ctime += 실행시간 # 누적 시간 갱신
        
        while len(waitq) > 0 and waitq[0][0] <= ctime: # 시간이 갱신 됐으니까 지나간게 있으면 작업 큐로 옮긴다.
            호출시각, 우선순위, 실행시간 = pop(waitq)
            push(taskq, (우선순위,호출시각,실행시간))
            
    answer[0] = ctime
    
    return answer

정확성  테스트
테스트 1 〉	통과 (3.67ms, 10.7MB)
테스트 2 〉	통과 (208.40ms, 21.5MB)
테스트 3 〉	통과 (101.01ms, 16MB)
테스트 4 〉	통과 (125.54ms, 16.9MB)
테스트 5 〉	통과 (168.41ms, 22.4MB)
테스트 6 〉	통과 (484.32ms, 31.7MB)
테스트 7 〉	통과 (7.44ms, 10.9MB)
테스트 8 〉	통과 (129.25ms, 19.8MB)
테스트 9 〉	통과 (130.05ms, 17.6MB)
테스트 10 〉	통과 (542.38ms, 33.1MB)
테스트 11 〉	통과 (529.98ms, 33MB)
테스트 12 〉	통과 (400.46ms, 33.1MB)
테스트 13 〉	통과 (376.77ms, 33.1MB)
테스트 14 〉	통과 (408.66ms, 33.2MB)

• 고수의 풀이. 코드 진짜 깔끔하다.

from queue import PriorityQueue

def call_programs(program, cur, q):
    while program and program[0][1] <= cur:
        q.put(program.pop(0))

def solution(program):
    answer = [0 for _ in range(10)]
    program.sort(key=lambda x: x[1])
    q = PriorityQueue() 
    cur = 0 

    while program or q.empty() == False: 
        if q.empty(): cur = program[0][1]
        else:  
            execute = q.get()
            answer[execute[0] - 1] += cur - execute[1]
            cur += execute[2] 

        call_programs(program, cur, q)

    return [cur, *answer]