스택/큐 > 프로세스

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

구현은 주어진데로 큐로 풀었다.

다만, 최대값에 대해서는 힙으로 변형하여 풀었다. 최대 힙 구조는 최상단에 항상 최댓값이 존재하기 때문에 현재 최우선도인 프로세스를 바로 구할 수 있다는 장점이 있다.

#include <queue>
#include <vector>
#include <utility> // for std::pair
using namespace std;

int solution(vector<int> priorities, int location) {
    queue<pair<int, int>> q; // (우선순위, 위치) 저장
    priority_queue<int> maxHeap; // 우선순위 확인용 최대 힙

    // 큐와 최대 힙 초기화
    for (int i = 0; i < priorities.size(); i++) {
        q.push({priorities[i], i});
        maxHeap.push(priorities[i]);
    }

    int order = 0; // 실행 순서

    while (!q.empty()) {
        int currentPriority = q.front().first;
        int currentIndex = q.front().second;
        q.pop();

        // 현재 프로세스가 최대 우선순위인 경우 실행
        if (currentPriority == maxHeap.top()) {
            order++;
            maxHeap.pop(); // 실행했으므로 최대 힙에서 제거

            if (currentIndex == location) {
                return order; // 찾는 위치의 프로세스 실행됨
            }
        } else {
            // 우선순위가 낮으므로 다시 큐에 삽입
            q.push({currentPriority, currentIndex});
        }
    }

    return -1; // 실행되지 않음 (논리적으로 여기 도달할 수 없음)
}