백준 1966 프린터 큐 C++

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

---

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

---

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

---

큐 자료구조는 FIFO의 순서로 처리를 합니다.

상근이는 새로운 프린터기를 만들었는데, 이 프린터기는 다음과 같은 방법으로 인쇄를 진행합니다.

 

1.현재 큐의 가장 앞에 있는 문서의 '중요도'를 확인합니다.

2.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고, 큐의 가장 뒤에 넣습니다. 그렇지 않은 경우 바로 인쇄를 시작합니다.

 

현재 큐에 있는 문서의 수와 , 중요도가 주어졌을 떄, 어떤 한 문서가 몇번쨰 순서에 인쇄되는지 알아내는 것이 목적입니다.

 

일단 테스트 케이스별로 N과 M을 입력받고, N개 문서의 중요도를 입력받습니다.

M번째 문서가 최종적으로 몇번쨰로 인쇄되었는지 구해야 하고, pair형태의 덱을 선언하고,

pair형태의 vector를 선언하였습니다.

 

그 후, 덱에 i번째 문서와 i번쨰 문서의 중요도를 넣어주었습니다.  {i, i번쨰 문서의 중요도 x}

 

   int t;
    cin >> t;
   
    while(t--){
        int n,m;
        cin >> n >> m;
        deque<pair<int,int>> v;
        deque<pair<int,int>>::iterator iter;
        vector<pair<int,int>> my_v;
        
        for(int i = 0;i<n;i++){
            int x;
            cin >> x;
            v.push_back({i,x});
        }

 

그 후, 덱이 비어있을 떄까지 진행되는데, bool변수 valid를 선언했고 이 bool변수의 목적은, 

현재 문서보다 중요도가 높은 문서가 있는지 판별하는 것입니다.

 

만약 현재 문서보다 중요도가 높은 문서가 존재한다면, valid를 true로 바꾸고, 

존재하지 않는다면, 바로 출력을 하면 됩니다.

 

덱의 첫번쨰 문서의 정보를 가져옵니다. (몇번쨰 문서인지, 해당 문서의 중요도)

  
            bool valid = false;
            
            int first_index = v.front().first;
            int first_value = v.front().second;

 

다음으로, 덱의 시작부터 끝지점까지 순회를 하면서, 문서의 중요도가 first_value보다 크다면, 

덱의 마지막에 첫번째 문서를 다시 넣어주고, 덱의 제일 처음을 pop합니다.

valid변수를 true로 바꿔줍니다.

 

  for(iter = v.begin();iter != v.end();iter++){
                
                int v_second_value = iter->second;
                if(v_second_value > first_value){
                    v.push_back({first_index,first_value});
                    v.pop_front();
                    valid = true;
                    break;
                }
            }

 

valid가 false인 경우 중요도가 더 큰 문서가 없는 경우이므로, 앞서 선언한 벡터에 넣어줍니다.

그리고 해당 문서를 출력했으므로, 덱의 제일 처음을 pop합니다.

 

 if(valid == false){
                my_v.push_back({v.front().first,v.front().second});
                v.pop_front();
            }

 

그 후, m 문서가 벡터의 몇번째 순서에 있는지 출력해주면 됩니다.

 

 for(int i = 0;i<my_v.size();i++){
            if(my_v[i].first == m){
                cout << i + 1;
                break;
            }
        }

 

전체 소스 코드->

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int main(void){
    
    int t;
    cin >> t;
   
    while(t--){
        int n,m;
        cin >> n >> m;
        deque<pair<int,int>> v;
        deque<pair<int,int>>::iterator iter;
        vector<pair<int,int>> my_v;
        
        for(int i = 0;i<n;i++){
            int x;
            cin >> x;
            v.push_back({i,x});
        }
        
  
        while(!v.empty()){
            
            bool valid = false;
            
            int first_index = v.front().first;
            int first_value = v.front().second;
            for(iter = v.begin();iter != v.end();iter++){
                
                int v_second_value = iter->second;
                if(v_second_value > first_value){
                    v.push_back({first_index,first_value});
                    v.pop_front();
                    valid = true;
                    break;
                }
            }
            if(valid == false){
                my_v.push_back({v.front().first,v.front().second});
                v.pop_front();
            }
        }
        
        for(int i = 0;i<my_v.size();i++){
            if(my_v[i].first == m){
                cout << i + 1;
                break;
            }
        }
        
        cout << '\n';
      

    }
       
    
}