[C++] 백준 1966번: 프린터 큐

문제

https://www.acmicpc.net/problem/1966

 

 

6 0 // N, K   1 1 9 1 1 // values

6개의 숫자 중에 0번째 숫자가 몇번째로 프린트 될까? 

 

주어진 숫자 중에 max는 9이다. 

9를 만나면 프린트를 하게 된다. 

 

1 1 9 1 1 1  // 1은 두번째로 큰 숫자이기 때문에 뒤로 보낸다.

1 9 1 1 1 1 

9 1 1 1 1 1 // 9는 가장 큰 숫자이기 때문에 출력된다. 출력 횟수 = 1

1 1 1 1 1 //  이제 가장 큰 숫자는 1이기 때문에 출력된다. 출력 횟수 = 2

1 1 1 1 //  출력 횟수 = 3

1 1 1 //  출력 횟수 = 4

 

1 1 //  출력 횟수 = 5

 

 

풀이

 

중요도 순서대로 pop 해야하기 때문에 중요도를 정렬 시켜야 한다. 

이건 라이브러리가 제공하는 priority queue를 이용하면 굳이 따로 정렬해주지 않아도 된다. 

 

문제에서 중요도가 중복될 수 있다는 점에 주의해야한다. 

1 1 9 1 1 1 에서 첫번째 1가 출력되는 순서가 중요하지 네번째 1 결과를 출력하지 않도록 주의해야한다. 

std::pair<index, value> 이렇게 짝 지어 queue에 넣고 풀어 해결했다. 

 

 

 

소스

 

#include <iostream>
#include <queue>

int main()
{
    int T= 0;
    std::cin >> T;
    
    while(T--)
    {
        int result = 0;
        int N=0, M=0, v=0;
        std::queue<std::pair<int, int>> q;
        std::priority_queue<int> sorted;
        
        //input
        std::cin >> N >> M;
        for(int i=0; i<N; ++i)
        {
            std::cin >> v;
            q.push(std::make_pair(i, v));
            sorted.push(v);
        }
        
        //solve
        while(!q.empty())
        {
            int index = q.front().first;
            int value = q.front().second;
            
            if(sorted.top() == value)
            {
                sorted.pop();
                ++result;
                if(index == M) break;
            }
            else
            {
                q.push(std::make_pair(index, value));
            }
            q.pop();
        }
        
        //output
        std::cout << result << std::endl;
    }
    
    return 0;
}

 

 

---

메모

index 배열 사용하는 것처럼 M의 인덱스를 따라갔더니 런타임 에러가 났다. 

 

 

#include <iostream>
#include <queue>
#include <algorithm>
int main()
{
    int T= 0;
    std::cin >> T;
    
    while(T--)
    {
        int result = 0;
        int N=0, M=0, v=0;
        std::queue<int> values;
        std::priority_queue<int> sort;
        
        //input
        std::cin >> N >> M;
        for(int i=0; i<N; ++i)
        {
            std::cin >> v;
            values.push(v);
            sort.push(v);
        }
        
        //solve
        int index = M; // target의 위치
        
        // 반복
        while(1)
        {
            int max = sort.top();
            if(values.front() == max)
            {
                values.pop();
                sort.pop();
                ++result;
                if(index == 0)
                {
                    break;
                }
            }
            else
            {
                int item = values.front();
                values.pop();
                values.push(item);
            }
            --index;
            if(index <0)
            {
                index = N;
            }
        }
        //
        
        
        
        //output
        std::cout << result << std::endl;
    }
    
    return 0;
}