백준1966 - 프린터 큐

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

1966번: 프린터 큐

꽤나 애먹었던 문제다.

큐를 deque할 때 가중치가 높은 것을 삭제하고 가중치가 같다면 앞에 위치한 것을 삭제한다.

현재 front에 있는 요소보다 가중치가 큰 요소가 있으면 현재 front를 rear로 보내고 두 번째 요소를 front에 위치시킨다.

이런 식으로 반복하면 내가 찾는 요소가 팝하는 순간이 온다. 그 순간에 몇 번째 pop한 요소인지 출력한다.

나는 큐에 pair를 이용하여 입력 시 두개의 숫자가 들어가도록 구현하였다.

pair중 첫번재 요소는 가중치이고 두번째 요소는 입력한 순서이다.

다음에 우선순위 큐를 이용해서 구현해 보아야겠다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	while (n--) {
		int cnt = 0; //몇번째 deque하는 원소인지 세는 변수이며 몇번째 가중치인지 나타내는 변수, 0부터 시작
		int a, b; //a는 입력할 갯수, b는 알고 싶은 문서의 번호
		int big; //현재 문서 중 가중치가 가장 큰 것
		vector<int> v; //가중치들을 담아놓을 변수
		queue<pair<int, int>>q; //문서에 가중치와 입력한 순서를 담을 변수
		cin >> a >> b;
		for (int i = 0; i < a; i++) { //0 ~ a - 1번째까지 입력, i는 문서를 넣는 순서
			int x; //문서의 가중치
			cin >> x;
			v.push_back(x); //가중치를 담는다.
			q.push(pair<int, int>(x, i)); //가중치와 입력한 순서를 담는다.
		}
		sort(v.begin(), v.end(), greater<int>()); //내림차순으로 정렬
		big = v[cnt]; //내림차순한 결과 가장 큰 원소를 저장한다.
		while (!q.empty()) { //큐를 순회
			if (big == q.front().first) { //가중치와 big의 값이 같다면
				if (q.front().second == b) { //현재 문서가 내가 찾는 문서라면
					cout << cnt + 1 << '\n'; //cnt + 1을 하여 출력(횟수는 1부터 시작)
					break; //탈출
				}
				//내가 찾는 원소가 아닌 경우
				big = v[++cnt]; //가장 큰 가중치를 변경한다.
				q.push(q.front()); //맨 앞에 원소를 맨 뒤로 이동
				q.pop(); //맨 앞에 원소 제거
			}
			else { //가중치와 big의 값이 같지 않을 경우
				q.push(q.front()); //맨 앞에 원소를 맨 뒤로 이동
				q.pop(); //맨 앞에 원소 제거
			}
		}
	}
}