[백준 1966번] 프린터 큐

🔗알고리즘 문제

이 문제에서는 기본적인 sort 알고리즘을 사용하지 못하고 중요도에 따라 새로운 정렬기준을 만들어 해결해야했다. 지금까지 누가 만들어놓은 로직만 사용하다 내가 직접 구현하려니 힘들었다. 그래도 이 문제를 해결하면서 자료구조에 대한 이해가 높아진 것 같아 기분이 좋았다

문제 분석

이 문제에서 궁극적으로 해결해야 할 일은 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다.

프린터 큐는 어떠한 규칙을 가지고 출력되는데 그 규칙은 다음과 같다.

1. 현재 프린터 큐의 가장 앞에 있는 문서의 중요도를 확인한다.
2. 프린터 큐에 안에 이 값보다 큰 값이 하나라도 존재한다면 현재 값을 프린터 큐의 가장 뒤에 재배치한다.
   그렇지 않다면 바로 인쇄 한다.

예를 들어 현재 Queue에 4개의 문서가 있고 중요도가 2 1 4 3 이라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 순서대로 인쇄하게 된다.

발상

이 문제의 핵심은 현재 프린터 큐의 가장 앞에 있는 문서의 중요도가 가장 높은 중요도인가를 판단하는 것 이다.

값을 판단하기 위해서 여러 고민을 하였는데 vector를 하나 더 만들어서 비교하는 방식으로 문제를 해결할 수 있었다. 생각해낸 방식은 다음과 같다.

vector1 - 원본 값이 담긴 원본 벡터
vector2 - 중요도가 오름차순으로 정렬된 벡터

- vector1의 가장 앞에 값이 vector2의 가장 뒤에 값과 동일하다면
* 현재 값이 가장 중요도가 높다.

- 그렇지 않다면
* 현재 값보다 높은 중요도를 가진 요소가 하나 이상 존재한다.

이런식으로 값을 판단할 수 있기에 문제를 해결 할 수 있었다.

알고리즘 설계

1. 프린터 큐가 모두 빌때까지 반복문을 돌며 값을 비교합니다.
2. 만약 프린터 큐의 가장 앞에 값이 정렬된 벡터의 가장 뒤에 값과 동일하다면
   현재 값을 출력 후 프린터 큐의 가장 앞에 값과 정렬된 벡터의 가장 뒤에 값을 제거합니다.
   그렇지 않다면
   현재 값을 벡터의 맨 뒤로 재배치 합니다.
3. 모든 테스트케이스를 반복합니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int Printer(int arraySize, int index, vector<int> printerQueue){
    vector<int> v = printerQueue;
    sort(v.begin(), v.end());

    while(!printerQueue.empty())
    {
        if(printerQueue.front() == v.back()){ // 이게 제일 큰수
            if(index == 0)
                return (arraySize - printerQueue.size()) + 1;

            printerQueue.erase(printerQueue.begin());
            v.erase(v.begin() + v.size() - 1);
        }
        else{
            printerQueue.push_back(printerQueue.front());
            printerQueue.erase(printerQueue.begin());

            if(index == 0)
                index = printerQueue.size();
            
        }

        index--;
    }

    return arraySize;
}

int main(){
    int testcase;
    int result[100];

    cin >> testcase;

    for(int i = 0; i < testcase; i++){
        int arraySize, index;
        vector<int> printerQueue;

        cin >> arraySize >> index;

        for(int j = 0; j < arraySize; j++){
            int input = 0;
            cin >> input;
            printerQueue.push_back(input);
        }

        result[i] = Printer(arraySize, index, printerQueue);
    }

    for(int i = 0; i < testcase; i++)
        cout << result[i] << "\n";
}