[프로그래머스] Level 2. 프로세스

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

프로그래머스

 

문제를 이해하는데 시간이 좀 걸렸다. 처음엔 priority_queue를 사용하여 쉽게 해결할 수 있을 줄알았는데,  queue에서 요소를 한개씩 빼서, 뒤에 나보다 우선순위 높은 작업이 있을 경우 다시 큐에 집어넣는 작업을 하나씩 수행해야 한다. 두번째 예제에서 처럼, 동일한 우선순위를 가진 작업의 순서에도 영향을 끼치기 때문이다. 

 

해결방법

1. 우선순위별로 작업이 몇개있는지를 저장하는 cnts을 선언한다. 이 맵은 우선순위 별로 자동으로 내림차순 정렬이 되게끔 선언했다.
2. 모든 프로세스를 돌면서 queue에 작업번호를 넣고,  cnts 에는 우선순위 개수를 저장한다.
3. 이제 queue에서 작업을 하나씩 빼면서, cnts 의 첫 번째 요소. 즉 현재 우선순위가 가장높은 작업을 찾는다. 우선순위는 element.first 이고, 남은 작업 개수는 element.second가 될것이다.
4. 만약 내가 꺼낸 작업이 최고우선순위보다 낮다면, 다시 큐에 집어넣고 넘어간다.
5. 만약 작업을 수행할 수 있다면, answer을 하나 올리고 , 남은작업리스트 cnts 에서 횟수를 줄여준다. 만약 횟수가 1이었다면, 아예 지워버린다.
6. 작업을 수행할 수 있을  경우, location과 비교하여, 내가 찾던 작업이라면 answer을  반환하고 종료한다.

 

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

map<int,int ,greater<int>> cnts; //내림차순 정렬
queue<int> q;

int solution(vector<int> priorities, int location) {
    int answer = 1;
    
    for(int i=0; i<priorities.size(); i++){
        q.push(i);
        int _pri = priorities[i];
        if(cnts.find(_pri) == cnts.end()) cnts.insert({_pri,1});
        else cnts[_pri] +=1;
    }
    
    while(!q.empty()){
        
        int index = q.front();
        q.pop();
        
        auto element = *cnts.begin(); //현재가장 우선순위높은작업
        if(element.first > priorities[index]) q.push(index); //더큰게있음.
        else { //뺄수있음.
            if(index == location) return answer; 
            
            if(cnts[element.first] ==1) cnts.erase(element.first);
            else cnts[element.first]-=1;
            
            answer++;
        }
    }
    
    return answer;
}