백준 1966 - 프린터 큐(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

Queue를 이용한 문제였습니다.

문제 조건

출력 예시

Queue에 중요도를 정하고 M번째 수가 언제 나오는지를 물어보는 문제였습니다.

Queue의 특징이 FIFO(First in first out)인 만큼 이를 활용하면 풀 수 있는 문제였습니다.

 

출력 예시 중, 예시 2번과 예시 3번을 활용해 정답을 도출해내는 과정을 확인해겠습니다.

2번 && 3번

저는 (순서, 중요도)를 저장하는 queue와 중요도를 저장하는 vector를 저장했습니다.

vector를 내림차순으로 정렬하여 queue의 front와 비교합니다. 이때 3가지의 경우의 수가 나오는데

1. queue의 front의 순서가 M과 같으며, 중요도가 vector의 cnt의 값과 같을때 -> 찾는 경우임으로 cnt를 출력한다.

2. queue의 front의 순서가 M과 다르고, 중요도가 vector의 cnt의 값과 다를때 -> 다른 경우임으로 넘어간다.

3. queue의 front의 중요도가 vector의 cnt와 다를때 -> 해당 경우를 push해 queue의 맨끝으로 옮긴다.

 

해당 과정을 반복함으로서 M번째 수의 출력 번호를 알 수 있습니다.

 

문제 접근 방법

1. 순서와 중요도를 queue에 저장하고 vector에는 중요도를 저장한다.

2. vector를 내림차순으로 정렬한다.

3. 3가지 경우를 확인하며 vector와 queue를 비교한다.

4. 해당 과정을 test_case 만큼 반복한다.

 

 

자세한 것은 코드를 참고해주세요

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;

int test_case;
int N, M;


int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for (int t = 0; t < test_case; t++) {
		cin >> N >> M;
		queue<pair<int, int>> input;
		vector<int> priority;
		for (int i = 0; i < N; i++) {
			int x;
			cin >> x;
			input.push(make_pair(i, x));
			priority.push_back(x);
		}
		sort(priority.begin(), priority.end());
		reverse(priority.begin(), priority.end());
		int cnt = 0;
		while (!input.empty()) {
			int number = input.front().first;
			int importance = input.front().second;
			input.pop();
			if (importance == priority[cnt] && number == M) {
				cout << cnt + 1 << "\n";
				break;
			}
			if (importance != priority[cnt]) {
				input.push(make_pair(number, importance));
			}
			else if (importance == priority[cnt] && number != M) {
				cnt++;
			}
		}
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요.