CodingTest Practice/Programmers

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

몽땅마니아(MDD) 2022. 5. 31. 15:54

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

 

코딩테스트 연습 - 프린터

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린

programmers.co.kr

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

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

정렬된 순서를 스택으로 담아서 풀어야 하나 했는데 내가 생각했던 방식대로라면 스택을 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;
}