#프린터

문제

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.

2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.

3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.

• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.

• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

풀이1 (priority_queue 사용)

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    
    queue<pair<int, int>> Q; //pair로 저장할 큐
    priority_queue <int> p_Q; //우선순위로 저장하는 큐

    for(int i=0; i<priorities.size(); i++)
    {
        Q.push(make_pair(i, priorities[i]));
        p_Q.push(priorities[i]);
    }
    
    int index = 0; //출력 순서를 알기위한 변수
    while(!Q.empty())
    {
        int current_index = Q.front().first;
        int current_value = Q.front().second;
        Q.pop();

        if(current_value == p_Q.top())
        {
            p_Q.pop();
            index++;
            if(current_index == location)
            {
                answer = index;
                break;
            }
        }
        else
            Q.push(make_pair(current_index, current_value));
    }
    
    return answer;
}

처음에 priority 큐를 몰라서 헤메다가 다른 사람들 풀이를 보고 알았다,,
코드 짜는건 비슷했는데 while문안에만 조금 달랐던,,

+) priority Queue 사용안하려면 max_element 사용하면 된다고 한다. 해보기!

풀이2 (max_element사용)

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    
    queue<int> Q; //priorities를 저장할 큐
    vector<int> sorted; //정렬된 큐 index 저장

    for(int i=0; i<priorities.size(); i++)
    {
        Q.push(i);
    }
    
    while(!Q.empty())
    {
        int index = Q.front();
        Q.pop();
        
        if(priorities[index] != *max_element(priorities.begin(), priorities.end()))
        {
            //max값이 아니라면 큐의 맨 뒤에 넣어주기
            Q.push(index);
        }
        else
        {
            //max값이 맞다면
            sorted.push_back(index);
            priorities[index] = 0; //비교되지 않게 0 넣어주기
        }
       
    }
    
    for(int i=0; i<sorted.size(); i++)
        if(location == sorted[i])
            answer = i+1; //index가 0부터 시작하므로 i+1
    
    return answer;
}