BOJ - 1966 - 프린터 큐

ggh·2022년 5월 11일

boj cpp ps queue

백준

목록 보기

19/112

BOJ - 1966 - 프린터 큐

문제

1966번: 프린터 큐

문제 개념

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

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

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

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

input

4 2
1 2 [3] 4

work flow

1 2 [3] 4
2 [3] 4 1
[3] 4 1 2
4 1 2 [3]
4 2 [3] 1
4 [3] 2 1

output

구현

#include <iostream>
#include <vector>
using namespace std;
/*
N
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)
M
몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 
output
궁금 문서의 입쇄 번수
input
3
1 0 - N = 1, M = 0 
5           output = 1
4 2 - N = 4, M = 2
1 2 [3] 4   output = 2
4 [3] 2 1 
6 0 - N = 6, M = 0
1 1 9 1 1 1 output = 5
workflow
[A] B C D E F
C D E F [A] B
1 2 3 4 [5] 6
output 
1 2 5
*/

int a = 0;
int main()
{
    int num; // test case
    int N;   // list size
    int M;   // 확인할 요소의 index 값    
    cin >> num;
    vector<int> answer;
    
    for(int i=0; i < num; i++)
    {
        cin >> N >> M;
        vector<pair<int, int>> q;
        for(int j=0; j < N; j++)
        {
            int temp;
            cin >> temp;
            // 우선순위, 초기 순서 
            q.push_back(pair<int, int>(temp, j));
        }
        /*
        work flow
        1 2 3 4
        2 3 4 1
        3 4 1 2
        4 1 2 3
        4 2 3 1
        4 3 2 1
        */
        for(int j=0; j < q.size(); j++)
        {
            for(int k=j; k < q.size(); k++)
            {   // 보다 큰 수를 찾으면 
                if(q[j].first < q[k].first)
                {   // j번째 값보다 큰수가 나올때 까지 pop후 맨 뒤 요소에 push
                    for(int l=0; l < abs(k - j); l++)
                    {   // 확인을 하지 않은 앞 요소 저장 
                        int fir = q[j].first;
                        int sec = q[j].second;
                        // 큐 pop 
                        q.erase(q.begin()+j);
                        q.push_back(pair<int, int>(fir, sec));
                        // work flow 출력 
                        // for(auto el : q)
                        //     cout << el.first << " ";
                        // cout << "," << k-j << endl;    
                    }
                    // j번 째 값보다 큰 수가 뒤에도 있을 경우를 대비하여 k값 초기화..
                    k = j;
                }
            }
        }
				// 문서의 출력순서 
        int count=0;
        for(int j=0; j < q.size(); j++)
        {
            if(q[j].second == M)
            {
                count++;
                answer.push_back(count);
            }
            else
                count++;
        }
    }
    //answer
    for(auto &el : answer)
        cout << el << '\n';
    return 0;
}

SOL

맨 앞 요소부터 오름차순으로 정렬하되 큐의 개념을 이용한다.
- work flow
- 1 2 [3] 4
- 2 [3] 4 1
- [3] 4 1 2
- 4 1 2 [3]
  - 0번째 index값을 리스트의 가장 큰 요소로 만들면 - 즉 오름차순이 된다면
  - 다음 요소로 넘어감..
- 4 2 [3] 1
- 4 [3] 2 1