프로그래머스 : 프린터 (C++, Lv.2, 큐)

https://programmers.co.kr/learn/courses/30/lessons/42587?language=cpp 

코딩테스트 연습 - 프린터

혼자 힘으로 풀긴 했지만 너무 많은 시간이 걸렸다 ㅜ

문제를 읽어보면 딱 봐도 큐를 이용해 목록을 탐색해야 한다는 걸 알았지만 정렬된 목록은 어떻게 담아야 할지에 대해 고민을 많이 했다.

정렬된 순서를 스택으로 담아서 풀어야 하나 했는데 내가 생각했던 방식대로라면 스택을 2개나 쓰는 비효율적인 코드만 생각났다. 

 

그러다가 이미 우선 순위에 대한 정보를 가지고 있다면 굳이 정렬된 목록에 넣었다 뺐다 하지 않아도 될 것 같다는 아이디어가 떠올라 아래와 같은 방식으로 구현했다.

다시 생각해보니 정렬된 목록은 큐가 아닌 벡터로 했어도 어차피 탐색만 할거라 상관 없었을 것 같다. 

 

소스코드

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

int prior[10];

int solution(vector<int> priorities, int location) {
    int answer = -1;
    
    //대기 큐(tmp) 과 정렬된 목록 큐(q)
     queue<pair<int, int>> tmp;
    queue<pair<int, int>> q;
    pair<int, int> p;
    
    
    //대기 큐에 모두 저장해두기
    for(int i = 0; i < priorities.size();i++) {
        prior[priorities[i]]++;
        tmp.push(make_pair(priorities[i],i));   
    }      
    //중요도 9부터 1까지 순차 진행
    for(int i = 9 ; i >= 1 ; i--) {
        // 해당하는 중요도의 문서가 남아있다면
        while(prior[i] > 0) {
            p = tmp.front();
            tmp.pop();
            //중요도가 같지 않으면 대기 큐에 넣기
            if(p.first != i) tmp.push(p);
            //중요도가 같으면 목록 큐에 넣기
            else {
                q.push(p);
                prior[i]--;
            }
        }
    }
    
    
    int index = 1;
    
    //목록 큐에서 요청한 문서가 몇 번째에 위치하는지 찾기
    while(!q.empty()) {
        p = q.front();
        if(p.second == location) {
            answer = index;
            break;
        }
        else {
            q.pop();
            index++;
        }
    }
    
    return answer;
}