문제

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

풀이

아이디어

• 일단 enumerate와 list comprehension을 사용하여 (priority, index)의 리스트를 만들고, 이를 deque로 만든다.
• 일차적으로, 가장 priority가 높은 프로세스가 deque의 가장 앞에 와야 하므로, 그 과정을 실행해준다.
• 일단 가장 높은 우선순위가 얼마인지를 maxPri에 저장해준다.
  • while: True
    • 지금 검사하는 프로세스가 우선순위가 가장 높다면 반복문을 탈출
    • 아니라면 deque를 rotate(-1)해서 deque의 가장 왼쪽것을 빼서 가장 오른쪽에 넣는 효과를 준다.
• 이차적으로, 위 과정으로 한 번 우선순위가 걸러진 deque를 다시 탐색하면서 processed라는 리스트로 하나씩 빼주는데, 이 중에서도 자기보다 우선순위가 높은 작업들이 뒤에 있다면, rotate(-1)을 해준다.
• 결과적으로 processed 리스트가 완성되면, 리스트를 탐색하며 문제가 원하는 location을 가지고 있는 프로세스를 반환하면 된다.

• 파이썬의 any와 all이 사용되었다. 이는 자바스크립트에서 Array.prototype.some()과 Array.prototype.every()에 매칭되는 기능들이다.
• 자바스크립트에서는 콜백함수를 넘겨주는 반면에 파이썬에서는 any와 all에 list comprehension으로 만들어진 리스트를 전달하는 식으로 사용된다.

코드

from collections import deque

def solution(priorities, location):
    queue = deque((v, i) for i, v in enumerate(priorities))
    maxPri = max(priorities)
    processed = []
    answer = 0
    
    # 최대 우선순위가 맨 앞에 올 때까지 rotate
    while True:
        cur = queue[0]

        if(cur[0] == maxPri):
            break
        
        if(any([cur[0] < q[0] for q in queue])):
            queue.rotate(-1)
            
    # 순서대로 꺼내면서 다시 정렬
    while(len(queue)):
        cur = queue[0]
        # 현재 아이가 제일 크다면
        if(all(cur[0] >= t[0] for t in queue)):
            processed.append(queue.popleft())
        # 아니라면, 뒤로 보낸다
        else:
            queue.rotate(-1)
    
    # 주어진 location에 해당하는 작업 찾기
    for i, p in enumerate(processed):
        if(p[1] == location):
            answer = i
            break

    return answer+1;