프로그래머스 42587 - 프로세스 (Lv.4)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/42587

// 프로그래머스 42587 - 프로세스 (Lv.4)
// https://school.programmers.co.kr/learn/courses/30/lessons/42587
// (같은 FIFO 골격: 42586 기능개발 — 다만 이쪽은 조건 미달이면 큐 뒤로 되돌린다)

// 문제 설명
// 운영체제는 다음 규칙으로 프로세스를 관리한다.
// 1) 실행 대기 큐에서 프로세스 하나를 꺼낸다.
// 2) 큐에 더 높은 우선순위의 프로세스가 남아 있으면 꺼낸 프로세스를 큐 뒤로 되돌린다.
// 3) 그렇지 않으면 실행한다.
// priorities 와 대상 프로세스의 인덱스 location 이 주어질 때, 그 프로세스가 몇 번째로
// 실행되는지 반환하라.

// 제약 조건
// 1 <= priorities 길이 <= 100
// 우선순위는 1 ~ 9 (숫자가 클수록 우선순위가 높다)
// 0 <= location < priorities 길이

// Example
// Input : priorities = [2, 1, 3, 2], location = 2
// Output: 1        (우선순위 3이 가장 높아 첫 번째로 실행)
//
// Input : priorities = [1, 1, 9, 1, 1, 1], location = 0
// Output: 5        (9가 먼저 나가고, 남은 1들은 큐 순서대로 → 대상은 5번째)

// 접근 — FIFO 큐 + 남은 최대 우선순위 조회
//
// [1단계 — 정렬하면 답이 사라진다]
// 우선순위만 보면 내림차순 정렬로 끝날 것 같지만, 동점 프로세스끼리의 순서가
// "큐에 남은 순서"로 결정된다. 예제 2에서 우선순위 1이 다섯 개인데 답이 5인 이유가 그것이다.
// 정렬은 이 순서 정보를 지워버리므로 대기열은 큐로 그대로 굴려야 한다.
//
// [2단계 — 인덱스를 함께 들고 다닌다 (자료구조 선택 근거)]
// 답으로 물어보는 것은 "값"이 아니라 "location 번째 원소가 몇 번째로 나가는가"다.
// 큐를 돌리면 원소의 현재 위치는 계속 바뀌므로 원래 인덱스를 잃으면 대상을 식별할 수 없다.
// → queue<pair<int, int>> 로 {우선순위, 원래 인덱스}를 묶어 넣는다.
//
// [3단계 — "더 급한 게 남아 있나"를 O(log n)으로 (자료구조 선택 근거)]
// 규칙 2)를 판정하려면 큐에 남은 최대 우선순위가 필요한데, 큐는 내부를 훑을 수 없다.
// 남은 프로세스의 우선순위만 따로 priority_queue<int> 에 담아 최댓값을 조회한다.
// 실행할 때만 pq.pop() 을 하므로 pq 의 내용은 항상 "아직 실행되지 않은 프로세스"와 일치한다.
// 되돌릴 때는 pq 를 건드리지 않는다 — 되돌린 프로세스도 여전히 남아 있는 프로세스다.
//
// [4단계 — 복잡도]
// 큐를 한 바퀴 돌면 최소 한 개는 실행되어 사라지므로 큐 연산은 최악 O(n^2),
// 우선순위 큐 연산은 O(n log n). n <= 100 이라 최악 1만 회 수준으로 여유가 크다.

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location)
{
    queue<pair<int, int>> q;       // {우선순위, 원래 인덱스} — 돌려도 대상을 식별할 수 있게
    priority_queue<int> pq;        // 아직 실행되지 않은 프로세스의 우선순위 (top = 남은 최댓값)

    for (int i = 0; i < priorities.size(); i++)
    {
        q.push({ priorities[i], i });
        pq.push(priorities[i]);
    }

    int order = 0;

    while (!q.empty())
    {
        auto [pri, idx] = q.front();     // 구조적 바인딩(C++17)
        q.pop();

        if (pri < pq.top())              // 더 급한 게 남아 있으면 실행하지 않고
        {
            q.push({ pri, idx });        // 큐 뒤로 되돌린다. pq 는 그대로 (여전히 남아 있으므로)
            continue;
        }

        pq.pop();                        // 실행 확정 — pri == pq.top() 이라 짝이 맞는다
        order++;

        if (idx == location) return order;   // 대상이 실행된 순간이 곧 답
    }

    return order;
}

정리

• 정렬로 끝날 것 같지만 동점 처리가 정렬을 막는다. 우선순위 내림차순으로 세우면 되는 문제처럼 보이는데, 같은 우선순위끼리의 순서는 값이 아니라 큐에 남아 있는 순서로 결정된다. 예제 2가 정확히 그 지점을 찌른다 — 우선순위 1이 다섯 개인데 답이 5인 것은 대상이 되돌려진 뒤 맨 뒤로 갔기 때문이다. 정렬은 이 정보를 지운다.
• 묻는 것이 “값”이 아니라 “위치”라서 인덱스를 값과 함께 들고 다녀야 한다. 큐를 돌리면 원소의 현재 위치가 계속 바뀌므로 location을 나중에 되찾을 방법이 없다. queue<pair<int, int>>로 {우선순위, 원래 인덱스}를 묶는 것이 이 문제의 실질적인 자료구조 결정이고, 위장(42578)의 해시맵처럼 자료구조를 탐색이 아니라 식별자 보존 용도로 쓰는 경우다.
• 큐는 내부를 볼 수 없으니 “남은 최댓값”은 별도 인덱스로 유지한다. priority_queue<int>에 남은 우선순위만 따로 담아 top()으로 조회한다. 여기서 실수하기 쉬운 지점은 되돌릴 때 pq를 건드리는 것 — 되돌린 프로세스도 여전히 남아 있는 프로세스이므로 pq는 그대로 둬야 하고, pop()은 실행이 확정되는 자리에서만 한다. 그 자리에서는 pri == pq.top()이 성립하므로 어떤 원소가 빠지는지 고민할 필요가 없다.
• 우선순위가 1~9로 좁다는 제약을 쓰면 int cnt[10] 카운팅으로 최댓값을 O(1)에 찾을 수도 있다. 값 범위에 기대는 만큼 빠르지만 범위가 바뀌면 무너지고, priority_queue는 범위와 무관하게 성립한다. 다이얼(5622)의 룩업 테이블처럼 값 범위가 좁을 때만 서는 최적화라는 점을 알고 고르는 것이 중요하다.
• 복잡도: 큐를 한 바퀴 돌 때마다 최소 하나는 실행되어 사라지므로 큐 연산은 최악 O(n²), 우선순위 큐 연산은 O(n log n). n <= 100이라 최악도 1만 회 수준. 커리큘럼 92번.
• 검증: 예제 2개(1, 5)와 경계 케이스 — 프로세스 1개(1), 동점 중 뒤쪽이 대상(2), 오름차순 입력에서 맨 앞이 대상(5) 통과 (MSVC /std:c++17 컴파일·실행).

핵심 요약 — 우선순위 내림차순 정렬로는 풀 수 없다. 동점끼리의 순서가 “큐에 남은 순서”로 결정되고 정렬이 그 정보를 지우기 때문이다(예제 2의 답 5가 그 증거). 순서는 FIFO 큐로 지키고, 큐가 내부를 볼 수 없는 문제는 priority_queue에 남은 우선순위만 따로 담아 top()으로 조회해 해결한다 — 되돌릴 때는 pq를 건드리지 않고 실행이 확정될 때만 pop()해야 “남은 집합”과 일치가 유지된다.