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

문제: www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

문제풀이

 

첫 번째로 문제에 접근한 방식은 큐와 배열을 선언하여 큐에는 pair로 문서의 인덱스, 중요도를 쌍으로 저장하고

배열에는 중요도를 저장 후 내림차순 정렬(sort 함수)하여 배열과 큐의 중요도를 비교했다.

 

 

- 중요도가 같을 때

 1. 목표 문서라면(인덱스가 같다면) 현재 출력 순서 출력 후 루프 종료

 2. 현재 가장 높은 중요도를 가진 문서이므로 pop() 후 출력 순서 증가, 배열 인덱스 증가

 

 

- 중요도가 다를 때

현재 큐의 front()에 있는 문서보다 높은 중요도를 가진 문서가 큐 안에 있으므로 현재 문서를 큐의 맨 뒤로 보냄

 

코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

bool compare(int num1, int num2){ //내림차순
    return num1>num2;
}

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

    int T;
    cin>>T;

    int N, M;
    queue<pair<int,int>> q;
    for(int i=0; i<T; i++){
        cin>>N>>M;
        int impo[N];
        for(int j=0; j<N; j++){
            cin>>impo[j];
            q.push({j, impo[j]});
        }
        
        sort(impo, impo+N, compare); //내림차순 정렬

        int result=1;
        int index=0;
        while(!q.empty()){
            if(impo[index]==q.front().second){ //중요도 검사
                if(q.front().first==M){ //인덱스까지 같으면 결과 출력 후 루프 종료
                    cout<<result<<"\n";
                    q = queue<pair<int,int>>(); //큐 초기화...
                    break;
                }
                q.pop();
                index++;
                result++;
            }
            else{
                q.push(q.front()); //중요도가 더 높은 문서가 있으므로 맨뒤로
                q.pop();
            }
        }
    }

    return 0;
}

 

결과

 

오답이 많은데 중간에 큐를 초기화를 안 해줘서 헤맸었습니다.