C++ / 프로그래머스 / 프로세스

문제

 

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

프로그래머스

문제풀이

 

가장 큰 중요도 먼저 꺼내야하므로, 우선순위 큐를 이용하여 중요도를 내림차순으로 정렬한다.

가장 큰 중요도를 꺼냈다면 처음으로 돌아가는 것이 아닌, 그 다음 프로세스 부터 탐색해야하므로 큐를 선언한다.

우선순위 큐는 중요도 내림차순, 큐는 현재 확인할 프로세스를 구하기 위함이다.

우선순위 큐에는 중요도만, 큐에는 중요도, 몇번째 프로세스인지를 입력한다.

 

우선순위 큐가 빌때까지, 반복문을 돌린다.

현재 큐 front에 있는 작업이 우선순위 큐에 있는 top과 같은 중요도라면 해당 작업을 한다.

이 때, 구하려는 location과 작업의 위치가 동일하다면 answer을 반환하면 된다.

동일하지 않다면 ++answer을 하고 다음 작업을 실행한다.

 

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer(0), idx(0), num(0);
    priority_queue<int>pq;
    queue<pair<int, int>>q;
    
    for (idx = 0; idx < priorities.size(); ++idx) {
        q.push({ priorities[idx],idx });
        pq.push(priorities[idx]);
    }

    while (!pq.empty()) {
        num = q.front().first;
        idx = q.front().second;
        q.pop();
        if (num == pq.top()) {
            ++answer;
            if (idx == location) return answer;
            pq.pop();
        }
        else {
            q.push({ num, idx });
        }
    }

    return answer;
}