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

✏️  문제 링크

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

 

✏️ 문제 설명

✏️ 로직

중요도와 순서를 저장할 수 있는 형태로 큐를 생성하기 ex) queue<pair<중요도, 처음 순서>>q 이제 이 큐를 탐색하게 되면 다음과 같은 경우로 나눌 수 있다.

1. q.front().first가 최댓값인 경우
   1. 이 경우에는 q.front.second()가 m이거나 m이 아닌 경우로 나누어진다
   2. q.front().second()가 m이라면 바로 order를 return, 일치하지 않는다면 order++하고 q.pop()을 통해 큐에서 해당 정보를 제거한다
2. q.front().first가 최댓값이 아닌 경우
   1. 이 경우에는 pair<int,int>로 q.front()값을 받은 뒤, q.pop()을 통해 제거를 하고 q.push()를 통해 ㅁ내 뒤로 재배치한다.

그럼 각 반복문의 단계에서 큐의 최댓값을 구하는 함수가 필요하다 findMaxValue(queue<pair<int,int>>q)라는 함수를 만들어서 q의 최댓값을 구한다.

✏️ 코드

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

int findMaxValue(queue<pair<int, int> > q) {
    int maxValue = -1;
    queue<pair<int, int> > data = q;
    while (!data.empty()) {
        pair<int, int> p = data.front();
        if (maxValue < p.first) {
            maxValue = p.first;
        }
        data.pop();
    }
    return maxValue;
}

int fun(int n, int m) {
    queue<pair<int, int> > q;
    int value, order = 1;
    for (int i = 0; i < n; i++) {
        cin >> value;
        q.push(make_pair(value, i));
    }

    while (!q.empty()) {
        pair<int, int> p = q.front();
        int maxValue = findMaxValue(q);

        if (p.first == maxValue) {
            // 현재 가장 맨 앞의 값이 최댓값인 경우
            if (p.second == m) {
                // 그 값이 m인 경우
                return order;
            }
            // 그 값이 m이 아닌 경우 -> 큐에서 제거
            q.pop();
            order++;
        } else {
            // 최댓값이 아니라면 재배치
            pair<int, int> p2 = q.front();
            q.pop();
            q.push(make_pair(p2.first, p2.second));
        }
    }
}

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

    int t, n, m;
    cin >> t;

    while (t--) {
        cin >> n >> m;
        cout << fun(n, m) << '\\n';
    }
}

✏️ 느낀 점

아무 생각 없이 큐에서 반복문을 돌린다고 for문을 적고 이게 왜 안될까?하고 생각을 하고 있었는데 생각해보니 queue라는 자료구조에서 for문을 돌린다는 게 정말 어리석은 생각이었다.

심지어 그 다음으로 한 생각은 iterator를 돌리자 ⇒ 이것도 말이 안되는데 queue는 단순히 FIFO를 지원하는 자료구조형태인데 여기서 iterator를 통해 모든 값을 탐색할 수 있으면 queue의 의미가 사라진다.

당분간은 자료구조 관련 문제를 풀면서 자료구조에 대해서 좀 더 공부를 해봐야 할 것 같다.

✏️ 결과