백준, BOJ, 1966번, 프린터 큐 C++ [CPP] ★★★★

// 2022.02.27 다시 품

 

어려운 문제는 아닌데..

정확하게 시키는대로 하는 것이 어렵다.

아니.. 하는 것이 어려운 것보다 우리가 짜는 알고리즘이 어떻게 진행될 지 정확하게 알아야 한다는 것이 포인트다.

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

1966번: 프린터 큐

 

---

 

큐를 이용하는 것 같지만.

 

여기서 중요한 조건이 뒤에 문서를 확인해야한다는 말이 있다.

 

즉, 탐색이 가능해야한다는 것이다.

스택, 큐는 전체 탐색이 불가능하다. 그렇게 만들어졌다.

때문에 전체 탐색이 가능하게 만들면서 큐의 성질만 구현해주면 된다.

 

나는 벡터를 선택했다.

이유는 없다.

 

 

#맞는 풀이

 

#include<iostream>
#include<vector> // queue 이용보다 탐색이 쉬움

using namespace std;

int tc; // 테스트 케이스 수

int main() {

    cin >> tc;

    //tc번 반복
    while (tc--) {

        //테스트에 쓰일 큐 생성(초기 위치, 중요도)
        vector<pair<int, int>> V;

        //인쇄 순서
        int cnt = 1;

        int numdoc, target; // 문서의 개수, 몇 번째로 인쇄되는지 알고 싶은 문서 위치
        cin >> numdoc >> target;

        //문서의 중요도를 차례대로 입력.(numdoc번 반복)
        for (int i = 0; i < numdoc; i++) {
            int priority;
            cin >> priority;

            //문서를 차례대로 입력
            V.push_back({i, priority});
        }


        //모든 문서를 출력할 때까지
        while (!V.empty()) {
            auto curdoc = V.front(); // 현재 출력될 문서
            int prior = curdoc.second; // 현재 문서의 중요도

            //현재 출력될 문서보다 중요도가 높은 문서가 있는지 조사
            for (auto doc : V) {
                //있으면 현재 출력될 문서 맨 뒤로 보냄
                if (prior < doc.second) {
                    V.push_back(curdoc); // 현재 맨 앞 문서 뒤로
                    V.erase(V.begin()); // 현재 맨 앞 문서 삭제
                    prior = 0;
                    //break를 넣지 않으면.. 한 번 인쇄 차례에 여러번 반복됨... 이거 때문에 시간날림 20분
                    break;
                }
            }
            //현재 출력될 문서가 제일 중요도가 높다면 인쇄
            if (prior != 0) {
                //그것이 타겟일 경우 몇 번째로 인쇄되는지 출력후, 다음 테스트케이스
                if (curdoc.first == target) {
                    cout << cnt << "\n";
                    break;
                }
                V.erase(V.begin());
                cnt++;
            }
        }
    }
}

 

 

여기서 중간 for 문 즉, 뒤에 있는 중요도 문서 확인에서 

break를 넣지 않아서 20분 날렸는데

 

break를 넣어야 하는 이유는 이렇다.

1,4,3,2 이고 나는 [2] 위치의 문서를 원한다.

 

현재 위치의 중요도는 1

벡터를 for문대로 순회하다보니 4라는 중요도가 나와서 4,3,2,1 로 바뀌었다.

순회는 끝나지않고 3이라는 중요도가 나와서 3,2,1,4, 로 바뀌었다.

????? 4가 맨앞인데 왜 또 뒤로가?

순회는 끝나지않았고 2라는 중요도가 나와서 2,1,4,3으로 바뀌었다.

?????? 

 

??? 뭔데??

즉 prior를 cur로 해놨지만

for문을 돌면서 cur이 갱신되지 않고 기존의 중요도인 1로 설정되었기 때문이다.

 

 

즉, 현재 값을 저장하고 이용할 때

현재 값을 비교로 어떠한 컨테이너를 수정할 때

현재 값이 바뀔 가능성이 있으므로

반복할 때마다 현재 값을 갱신해주지 않으면 오류가 날 수 있음

 

오늘 크게 데었다.

 

---

 

#22.02.27 10분만에 푼 풀이..?

어떤 것에 대해 상태를 체크할 때

map을 쓰는 것이 극도로 효율적이라는 것을 깨닫고 나서 푸니까... 바로 풀었다.

#include <bits/stdc++.h>

using namespace std;

int T;


int main(){
    cin >> T;
    while(T--){
        int N, M; // N개의 문서가 있고, M번째 문서가 몇번째로 출력될까?
        cin >> N >> M;
        unordered_map<int, int> check;
        //N개의 문서의 중요도
        queue<pair<int,int>> q;
        for(int i = 0; i<N; i++){
            int x;
            cin >> x;
            q.push({x,i}); //x중요도를 가지는 i번째 문서
            check[x]++; //해당 중요도를 가지는 문서의 개수 추가.
        }
        
        //출력하는 순서 - seq;
        int seq = 0;
        while(!q.empty()){
            auto cur = q.front(); //현재 맨 앞의 문서, 중요도
            bool canPrint = true;
            //나보다 중요도 높은 문서가 남아있으면 출력x
            for(int i = cur.first + 1; i<=9; i++){
                if(check[i] > 0){
                    canPrint = false;
                    break;
                }
            }
            if(canPrint){
                seq++;
                q.pop();
                check[cur.first]--;
                if(cur.second == M){
                    cout << seq << '\n';
                    break;
                }
            }else{
                q.pop();
                q.push(cur);//맨 뒤로 보냄.
            }
        }
    }
    
    
    return 0;
}