[C++]프로그래머스 프로세스

코딩테스트 연습 - 프로세스 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

#include <string>
#include <vector>
#include <queue>

using namespace std;

struct process {
    int prio;
    int idx;
};

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<process> q;
    priority_queue<int> pq;
    for(int i=0;i<priorities.size();i++) {
        q.push({priorities[i],i});
        pq.push(priorities[i]);
    }
    
    while(!q.empty()) {
        if(q.front().prio==pq.top()) {
            answer++;
            if(q.front().idx==location) break;
            q.pop();
            pq.pop();
        }
        else {
            q.push(q.front());
            q.pop();
        }
    }
    
    return answer;
}

구해야하는 인덱스의 위치와, 그 인덱스가 몇번째로 pop되는지,

각 숫자들의 우선순위와 인덱스가 같이 움직여야 했던 문제였음

1.queue가 두 값을 들고 있는 형태여야함

2.매 실행마다 현재 queue의 가장 큰 값을 구할 수 있어야 함

두 가지 조건을 만족해야 하는데

priority_queue를 사용하면 자동으로 큰 값부터 정렬이 되기 때문에 pq.top()은 항상 가장 큰 수가 된다.

결국 우리가 구해야하는 인덱스가 pop되는 조건은 그 인덱스가 max값이 될 때이므로

while문을 돌려주면서 answer을 증가시켜주다가 인덱스가 max값이 될 때 우리가 구해야하는 인덱스이면

answer의 증가를 멈춘다. 그것이 곧 답이 된다.

 

방법은 한 가지만이 아니다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct process {
    int prio;
    int idx;
};

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<process> q;
    for(int i=0;i<priorities.size();i++) {
        q.push({priorities[i],i});
    }
    int max = *max_element(priorities.begin(), priorities.end());
    while(!q.empty()) {
        if(q.front().prio==*max_element(priorities.begin(), priorities.end())) {
            answer++;
            int index = q.front().idx;
            if(q.front().idx==location) break;
            q.pop();
            priorities[index] = 0;
        }
        else {
            q.push(q.front());
            q.pop();
        }
    }
    
    return answer;
}

매 실행마다 *max_element를 이용해서 가장 큰 수를 구하고 

pop이 되었으면 해당하는 인덱스를 priorities[인덱스] = 0에 넣어주면서 max값을 변화시킨다.