BOJ 1966 - 프린터 큐

프린터 큐 - 🥈 Silver 3

• 문제 링크
  https://www.acmicpc.net/problem/1966

queue를 활용하는 문제이다. queue는 First In First Out, 다시 말해 FIFO 자료구조이며, 이를 이용해 중요도에 따라 순서대로 출력물을 프린트하는 문제이다.

풀이한 순서는 아래와 같다.

1. 문서를 해당 index와 동일하게 이름을 가정해 queue에 순서대로 삽입
2. index에 맞게 각 문서의 중요도를 입력받아 vector에 저장
3. 동시에 다른 vector에 각 난이도에 따른 문서의 개수를 count
4. 원하는 문서가 출력될때까지 아래를 반복
   • 중요도에 따른 문서의 개수를 저장한 vector를 순회하여 더 높은 중요도의 문서가 있는지 확인
   • 존재한다면 가장 앞에서 문서를 pop하여 가장 뒤에 push
   • 존재하지 않는다면 해당 문서 print + 출력 횟수 count
   • 출력하려는 문서가 출력 순서를 알고싶은 문서라면 반복문 종료 이후 출력 횟수 출력

이에 대한 풀이 코드는 아래와 같다.

풀이 코드

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

int T, N, M, value, target, counter;
deque<int> queue;
vector<int> importance;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
    // test case 수 입력받아 반복
	cin >> T;
	while (T--) {
    	// 문서의 개수 N과 원하는 문서의 위치 M을 입력받음
		cin >> N >> M;
		
        // 1부터 9까지의 중요도에 대한 문서의 개수를 저장할 vector
		vector<int> importanceCounter(10, 0);
        
        // 중요도 입력받음
		for (int i = 0; i < N; i++) {
			queue.push_back(i);
			cin >> value;
			importance.push_back(value);
			importanceCounter[value]++;
		}
        
		target = M;
		
		while (true) {
        	// queue 가장 앞에 있는 문서가 출력이 가능한지 판단할 bool
			bool canPrint = true;
            
            // 가장 앞 문서 중요도부터 9까지 탐색
			for (int i = importance[queue.front()] + 1; i <= 9; i++) {
           		// 더 중요한 문서가 있을 경우 프린트 불가능
				if (importanceCounter[i] != 0) {
					canPrint = false;
					break;
				}
			}
			
            // 프린트가 가능한 경우
			if (canPrint) {
            	출력 횟수를 1 증가시고 해당 중요도 문서 개수 1 감소
				counter++;
				importanceCounter[importance[queue.front()]]--;
                // 출력하려는 문서가 해당 문서일 경우 반복문 종료
				if (queue.front() == target) {
					break;
				}
				queue.pop_front();
			}
            // 프린트가 불가능한 경우
			else {
            	// 가장 앞 문서를 가장 뒤로 보내고 계속
				queue.push_back(queue.front());
				queue.pop_front();
			}
		}
		
        
        // 결과 출력과 변수 초기화
		cout << counter << "\n";
		queue.clear();
		importance.clear();
		counter = 0;
	}
}

결과