[스택/큐, 난이도 중하] 프로그래머즈, 프린터

문제의 조건을 보고 스택,큐중 어느 것을 요구하는지 파악해보자.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.  2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.  3. 그렇지 않으면 J를 인쇄합니다.

'앞', '마지막' 이라는 단어가 나오는 것을 보아 큐 문제임을 알 수 있다.

 

그리고 둘 이상의 문서끼리 중요도가 같을 수 있고, 문서의 인덱스까지 신경써줘야 하는 문제이다.

그래서 큐에 문서의 중요도, 인덱스 두 정보를 pair을 이용해 정리했다.

 

문서는 최대 100개 있고, 중요도는 1~9의 정수로 표현할 수 있다.

J보다 중요도가 높은 문서를 찾기 위해 큐에 있는 모든 요소를 확인하는 것 보다는, 중요도별로 몇 개의 문서가 있는지 카운트 해두고 J보다 중요도가 높은 문서들의 카운트가 전부 0이라면 J를 인쇄 처리하는 방법이 훨씬 효율적이다.

 

J를 인쇄 해야 하는 경우에는 J문서의 중요도를 가지는 문서들의 개수 카운트를 1 감소시키고,
J를 인쇄 하지 않고 마지막으로 보내야 하는 경우에는 다시 큐에 push해주는 과정을 반복하면 된다.

 

[테스트 케이스 20개 모두 통과]

 

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

int prioritycount[10]; //중요도 별 문서 수 카운트
int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<pair<int, int> > q; //중요도, 인덱스 pair
    for(int i=0;i<priorities.size();i++){
        q.push(make_pair(priorities[i],i));
        prioritycount[priorities[i]]++;
    }
    while(!q.empty()){
        int f = q.front().first;
        int fi = q.front().second;
        q.pop();
        bool ismax=true;
        //J보다 높은 우선순위를 가지는 문서가 남아있는지 확인
        for(int i=f+1;i<10;i++) if(prioritycount[i]>0) ismax=false;
        if(ismax){
            answer++;
            if(fi==location) return answer;
            prioritycount[f]--; //카운트1 감소
        }
        else q.push(make_pair(f,fi)); //다시 마지막으로 push
    }
    return answer;
}