[프로그래머스] 프로세스 (Level 2)

---

풀이 과정

예제 2번을 살펴보자.

priorities = [1, 1, 9, 1, 1, 1]
location = 0

초기 큐는 다음과 같다.

[(0, 1), (1, 1), (2, 9), (3, 1), (4, 1), (5, 1)]

먼저 (0, 1)을 꺼낸다.

큐 안에 우선순위 9가 있으므로 다시 뒤에 넣는다.

[(1, 1), (2, 9), (3, 1), (4, 1), (5, 1), (0, 1)]

마찬가지로 (1, 1)도 뒤로 간다.

[(2, 9), (3, 1), (4, 1), (5, 1), (0, 1), (1, 1)]

이제 (2, 9)를 꺼낸다.
큐 안에 더 높은 우선순위가 없으므로 실행된다.

실행 순서:

1번째 실행: 위치 2

이후 나머지 우선순위는 모두 1이므로 큐 앞에서부터 차례대로 실행된다.

2번째 실행: 위치 3
3번째 실행: 위치 4
4번째 실행: 위치 5
5번째 실행: 위치 0

따라서 location = 0인 프로세스는 5번째로 실행된다.

---

전체 코드

from collections import deque

def solution(priorities, location):
    queue = deque()

    for i, priority in enumerate(priorities):
        queue.append((i, priority))

    answer = 0

    while queue:
        current_index, current_priority = queue.popleft()

        has_higher_priority = False

        for _, priority in queue:
            if priority > current_priority:
                has_higher_priority = True
                break

        if has_higher_priority:
            queue.append((current_index, current_priority))
        else:
            answer += 1

            if current_index == location:
                return answer

---

더 간단한 코드

any()를 사용하면 더 짧게 작성할 수 있다.

from collections import deque

def solution(priorities, location):
    queue = deque((i, priority) for i, priority in enumerate(priorities))
    answer = 0

    while queue:
        current_index, current_priority = queue.popleft()

        if any(priority > current_priority for _, priority in queue):
            queue.append((current_index, current_priority))
            continue

        answer += 1

        if current_index == location:
            return answer

---

시간 복잡도

프로세스의 개수를 N이라고 하자.

큐에서 프로세스를 하나 꺼낼 때마다, 큐 안에 더 높은 우선순위가 있는지 확인한다.

이 확인 과정은 최악의 경우 O(N)이 걸린다.

프로세스는 여러 번 뒤로 밀릴 수 있지만, N <= 100으로 매우 작기 때문에 단순 시뮬레이션으로 충분하다.

전체 시간 복잡도는 보통 다음과 같이 볼 수 있다.

O(N^2)

공간 복잡도는 큐에 프로세스 정보를 저장하므로 다음과 같다.

O(N)

---

정리

이 문제는 큐의 동작을 그대로 구현하는 시뮬레이션 문제다.

중요한 점은 같은 우선순위를 가진 프로세스가 있을 수 있으므로, 우선순위만 저장하면 안 된다는 것이다.

따라서 각 프로세스의 초기 위치와 우선순위를 함께 저장하고, 실행될 때마다 초기 위치가 location인지 확인하면 된다.