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

이 요상한 큐 문제는 각 요소마다 중요도가 있어서, 자기보다 더 중요한 요소가 존재하면 무조건 맨 뒤로 이동시키게 된다. 그래서 지정된 요소가 몇 번째로 출력이 되는가를 알아내는 프로그램을 작성하는 것이 이 문제의 목적이 되시겠다.

 

문제를 풀기 전에 고려했던 것은 어떤 컨테이너를 쓸 지였는데, 일반 queue를 쓰자니 중요도를 상호간 비교할 수가 없을 것 같아서 결국엔 앞뒤 push, pop이 되고 iterator를 사용할 수 있는 deque를 사용하기로 했다.

 

#include <iostream>
#include <deque>
using namespace std;

int main(void) {
    int n;
    scanf("%d", &n);	//총 몇 번을 수행할 것인지
    for(int i = 0; i < n; i++)
    {
        deque<int> dq;	//덱 생성
        int N, M, t = 0;	//t는 몇 번째로 출력되는지 저장할 변수
        cin >> N >> M;	//N은 큐의 원소 개수, M은 파악해야 될 원소의 위치
        for(int j = 0; j < N; j++)	//N만큼 요소 개수를 입력 받기
        {
            int elem;
            cin >> elem;
            dq.emplace_back(elem);	//덱의 맨 뒤에 삽입
        }
        auto pt = &dq.at(M);	//M번째 요소의 주소를 저장하는 변수 pt
        while(!dq.empty())	//일단은 덱이 비어있지 않는 동안 실행
        {
            bool prior = true;	//우선 순위가 제일 높을 때 true
            for(auto it = dq.begin()+1; it < dq.end(); it++)	//iterator를 통해 순환
            {
                if(*it > dq[0])	//만약 맨 앞에 있는 요소의 중요도보다 iterator가 가리키는 요소의 중요도가 더 클 때
                {
                    prior = false;	//우선 순위가 제일 높지 않으므로 false
                    break;	//for문 탈출
                }
            }
            if(prior == true)	//맨 앞에 있는 요소가 우선순위가 제일 높을 때
            {
                t++;	//몇 번째로 출력하는지 나타내는 변수 1 증가
                if(pt == &dq.front())	//만약 알아내야 하는 변수가 맨 앞이었을 때
                {
                    dq.pop_front();	//맨 앞의 요소를 pop
                    break;	//Outer while loop 탈출
                }
                else	//알아내야 하는 변수가 맨 앞이 아닐 때
                    dq.pop_front();	//그냥 맨 앞 요소 pop
            }
            else	//맨 앞에 있는 요소가 우선순위가 제일 높지 않을 때
            {
                dq.emplace_back(dq.front());	//맨 앞 요소 맨 뒤에 push
                if(pt == &dq.front())	// 알아내야 하는 요소의 주소가 맨 앞이었을 때
                    pt = &dq.back();	//주소를 맨 뒤 요소로 다시 설정해줌
                dq.pop_front();	//맨 앞 요소 pop
            }
        }
        printf("%d\n", t);	//t로 몇 번째로 탈출하는지 출력
    }
    return 0;
}

이번 문제에서는 어떻게 M번째 요소를 예의주시할 것인가가 관건이었던 것 같다. 나는 M번째 요소의 주소값을 변수에 저장해서 추후에 비교하는 식으로 해결했다.

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

1966번: 프린터 큐