[백준 1966번] [큐] 프린터 큐

이 문제를 보고 큐(Queue)형태의 자료라는 것을 파악했어야 한다.

왜냐하면, 선입선출 형태로 자료를 호출하기를 요구하고 있기 때문이다.

 

다만, 이 문제에서는 독특한 지점이 단순히 선입 선출을 활용할 수 없고 중요도를 기준으로 다시 재배치해야한다는 점인데

중요도가 맨 앞에 위치한 것이 최대가 아니면 pop시키고 다시 그 수를 push해주면 된다.

 

추가적으로 m번째 숫자를 따로 저장을 해 두어야하기 때문에 pair자료형을 활용하여 해당하는 자료형을 구분한다.

(문제에서 같은 숫자가 등장할 수 있다고 하였으므로, 같은 숫자를 구분하려면 어쩔 수 없이 pair자료형을 활용하여 추가적인 자료형을 도입하여 구분해야 한다.)

 

위의 알고리즘을 활용하여 코드를 구현하면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstdlib>
#include <queue>

using namespace std;

int main(void){
    int num;
    cin >> num;
    
    for(int i = 0; i < num; i++){
        int n, m;
        cin >> n >> m;
        int count = 1;
        queue<pair<int,int> > data_store;
        for (int j = 0; j < n; j++){
            int temp;
            cin >> temp;
            pair<int, int> temp_store;
            temp_store.first = temp;
            if (j == m){
                temp_store.second = 1; // 문제에서 요구한 m번째를 따로 체크
            }
            else{
                temp_store.second = 0; // Default case setting
            }
            
            data_store.push(temp_store);
        } // store data

        // 문제에서 요구한 케이스가 나올때까지 계속해서 맨 앞을 수정

        while(data_store.size() -1 != 0){
            queue<pair<int,int> > temp = data_store;
            int front = temp.front().first;
            bool check = true;
            
            // Front에 놓인 숫자가 max값인지 확인하는 작업
            for(int j= 0; j < data_store.size() - 1; j++){
                temp.pop();
                if(front < temp.front().first){
                    check = false;
                    break;
                }
            }

            // 맨 앞에 놓인 숫자가 max인 경우

            if (check == true){
                if(data_store.front().second == 1){
                    break; // 맨 앞에 놓인 숫자가 내가 고르고자 하는 수인 경우
                }
                else{
                    data_store.pop();
                    count += 1; // 아닌 경우 >> 나머지 숫자들을 가지고 다시 반복
                }
            }

            // 맨 앞에 놓인 숫자가 max가 아닌 경우

            else{
                pair <int, int> temp_num = data_store.front();
                data_store.pop();
                data_store.push(temp_num); // 맨 앞에 놓인 숫자를 뒤로 배치시킨다.
            }
        }
        cout << count << "\n"; // 문제에서 요구하는 값 출력
    }

    return 0;
}

추가적으로 아직 학습하지는 않았지만, 우선순위 큐를 활용해서 푸는 방법도 있다고 하니 학습해 두도록 하자.

학습해야할 것: 트리, 우선순위 큐