백준 1966번 - 프린터 큐 문제 C++ [Queue]

📍 백준 1966번 - 프린터 큐 문제 C++ [Queue]

---

🧩문제 요약

<Queue>

T개의 testcase가 주어진다. 

입력되는 숫자의 갯수 n과 관심있는 숫자의 인덱스 번호 m이 입력된다.

prioiry_queue와 동일하게 중요도를 기준으로 중요도가 높은 것 부터 출력이 된다고 할때, 관심있는 m번째 숫자는 몇번째로 출력이 되는가?

---

🧾내가 작성한 초기 코드 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std; 

bool compare(int a, int b){
    return a > b; 
}

int main(){
    int t, n, m, num, nums[101], find_num;
    cin >> t; 
    while(t--){
        cin >> n >> m ;
        priority_queue<pair<int,int>> pq;
        for(int i = 0; i<n; i++){
            cin >> num;
            pq.push({num, i});
        }
        for(int i = 0; i<n; i++){
            auto top = pq.top();
            pq.pop();
            if(top.second==m){
                cout << i+1 << "\n";
            }
        }
    }
}

---

👍이 문제에서 배운점

처음에는 priority_queue를 알려주는 간단한 문제인줄 알고 간단하게 풀었다. 

그런데 계속 정답이 안나오고 공개된 testcase에서도 다른 값이 나왔다. 

무엇이 문제인지 한참 감을 못잡고 있었는데 문제는 바로 Queue를 pair로 입력받은 것에 있었다. 

😕 문제점 1. 

우선순위 queue에 두가지 이상의 값을 입력할 때, 첫번째가 같으면 그다음 요소로 중요도 순서를 매긴다.

 

이게 무슨말인가 하면 만약에 1을 다섯개 입력한다고 하면,

나는 1이라는 값과 입력된 순서대로 인덱스 번호를 Queue에 같이 push 했다.

 

그러면 queue에는 {1, 0}, {1, 1},  {1, 2},  {1, 3},  {1, 4}가 입력되고 첫번째 요소가 모두 같은 값이기 때문에 그 다음 요소를 가지고 중요도를 측정한다. 그러면 Queue에는 다음과 같은 순서대로 값들이 정렬되게 된다. {1, 4}, {1, 3},  {1, 2},  {1, 1},  {1, 0}

 

그래서 문제에 나온 testcase 3번 같은 경우 1, 1, 9, 1, 1, 1에서 0번째 인덱스가 언제 출력하는지 보려고 하면 제대로 출력이 안되는 문제가 생겼다.

 

priority_queue입장에서는 올바르게 일한것이지만, 내가 원하는 출력값은 아니였다. 

 

 

✅ 직접구현

그래서 priority_queue 를 사용하지 않고 그냥 queue를 사용하여 직접 정렬을 하는 방식으로 코드를 구현했다. 

 

완성된 코드는 아래와 같다. 

---

🧾 완성된 코드 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std; 

bool compare(int a, int b){
    return a > b;
}

int main(){
    int t; 
    int arr[101];

    // TEST case입력받기 
    cin >> t; 
    
    while(t--){
        int n, m, input, answer=1;
        // 문서 갯수, 궁금한 문서 입력받기
        cin >> n >> m ;
        queue<pair<int,int>> q; 

        // 문서 중요도 입력값 받기 
        for(int i =0; i< n ; i++){
            cin >> input;
            arr[i] = input; 
            q.push({input, i});
        }
        int find_doc = arr[m];
        sort(arr, arr+n, compare);
        // 궁금한 문서가 출력될 차례인지 q가 빌때까지 확인
        // 궁금한 문서 찾으면 loop 종료 
        for(int i = 0; i<n; i++){
            while(1){
                auto t = q.front() ;
                if(arr[i]==find_doc && t.second==m){
                    cout << answer << "\n";
                    q.pop();
                    break ;
                }
                else if(t.first == arr[i]){
                    q.pop();
                    answer++;
                    break; 
                }
                else{
                    auto tmp = q.front();
                    q.pop();
                    q.push(tmp);
                }
            }
        }   
    }
    return 0;
}

---

정말 다른 사람의 풀이를 보지 않고 해결하고 싶어서 오랫동안 붙잡고 있었던 문제이다. 

간단한듯 하면서도 안풀리니까 오기가 생겼던것 같다. 

 

다른 풀이들을 보니 훨씬 더 간단한 코드들이 많지만 내 힘으로 고민하며 풀었다는 것에 매우 만족한다. ㅎㅎ