BOJ 1966 c++ 프린터 큐

BOJ 1966 프린터 큐 c++

백준 1966 cpp 프린터 큐

 

문제 링크 : https://www.acmicpc.net/problem/1966

 

정답률이 높았음에도 불구하고 필자에겐 설계에 꽤 많은 시간이 걸린 문제였다. 문제를 해결할 수 있었던 가장 핵심이 된 아이디어는 Queue에 하나씩 담을 때 목표가 되는 녀석을 표시해놓기 위해 int 형 queue가 아닌 pair<int, char> 형으로 Queue를 선언했다. 그래서 담을 때 목표가 되는 녀석은 char 부분에 't'를 담고 나머지는 전부 공백을 담았다.

 

시간도 2초로 넉넉하고 N도 100이하, 중요도도 1~9 사이었기에 시간 복잡도는 고려하지 않았다. 큐의 맨 앞에 있는 요소를 확인할 때마다 getMaxNumber함수를 호출해 큐를 처음부터 끝까지 돌았고, 가장 큰 숫자가 나올 때에만 cnt를 증가시켰다. 가장 큰 숫자가 아닌 경우에는 큐의 뒤로 보내버렸다. 그리고 가장 큰 숫자가 나왔을 때 pair의 char부분이 't'인 경우 출력해버리고 다음 테스트케이스로 넘어가도록 했다. 당연히 넘어갈 때 Q는 새로운 정보를 받아야 하므로 Q를 비워주는 과정도 거쳤다.

 

#include <bits/stdc++.h>
using namespace std;

queue<pair<int, char>> Q;

int getMaxNumber(void)
{
    int maxNumber = -1;
    queue<pair<int, char>> tempQ = Q;
    while (!tempQ.empty())
    {
        maxNumber = max(tempQ.front().first, maxNumber);
        tempQ.pop();
    }
    return maxNumber;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    int testcaseCount;
    cin >> testcaseCount;

    while (testcaseCount--)
    {
        cin >> N >> M;
        int cnt = 0;
        for (int i = 0; i < N; i++)
        {
            int paper;
            cin >> paper;
            if (i == M)
                Q.push({paper, 't'});
            else
                Q.push({paper, ' '});
        }
        while (true)
        {
            if (Q.front().first == getMaxNumber())
            {
                cnt++;
                if (Q.front().second == 't')
                {
                    cout << cnt << '\n';
                    while (!Q.empty())
                        Q.pop();
                    break;
                }
                else
                    Q.pop();
            }
            else
            {
                pair<int, char> p = Q.front();
                Q.pop();
                Q.push(p);
            }
        }        
    }
}