프린터

문제설명

 

 

입출력 예 

 

 

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 1;
    queue<pair<int,int>> arr; //first : priority, second : index
    priority_queue<int> priQue;
    
    for(int i=0; i<priorities.size(); i++)
    {
        pair<int,int> tmp =make_pair(priorities[i], i);
        arr.push(tmp);
        priQue.push(priorities[i]); //자동으로 큰순으로 정렬됨
    }
    
    while(!arr.empty())
    {   
        pair<int,int> tmp = arr.front();
	    arr.pop();
        if(tmp.first == priQue.top())
        {
            if(tmp.second == location)
            {
                break;
            }
            else
            {
                answer++;
                priQue.pop();
            }
        }
        else
        {
            arr.push(tmp);
        }
    }
    return answer;
}

 

 

=> queue와 priority queue를 사용하는 문제입니다. 

=> priority를 사용하지 않을 경우 매번 지금 queue에 남아 있는 원소들 중 priority가 가장 높은 아이가 누구인지를 for문을 통해 찾아야 합니다. 

=> 저는 이런방식을 사용하려 했지만, 오류가 나였으며 우선순위 큐를 사용할 경우 삽입과 삭제의 경우 항상 정렬되어있는 우선순위 큐를 사용하는 것이 좋다는 것을 알았습니다. 

=> 현재 queue의 front에 있는 값과 우선순위 큐에 있는 front와 일치하며 내가 찾는 location과 일치하는 경우 while문을 나오게 됩니다. 

=> 현재 queue의 front에 있는 값과 우선순위 큐에 있는 front와만 일치하는 경우 횟수를 증가시키고, queue와 우선순위 큐에서 해당 값을 pop 시킵니다. 

=> 둘다 아닌 경우 queue의 front값을 pop 한 후, 다시 push 합니다. 

 

 

**우선순위 큐와 HEAP의 개념을 미리 알아두면 쉽게 풀 수 있는 문제였습니다.