[1966번] 프린터 큐

1966번: 프린터 큐

 

www.acmicpc.net

/*1966번 프린터 큐*/
#include <iostream>
#include <vector>
using namespace std;
struct info {
	bool target;
	int priority;
}temp;
vector<info>Q;
int T, N, M, cnt = 1, break_flag;
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> N >> M;
		for (int i = 0; i < N; i++) {
			int input;
			cin >> input;
			if (i == M) {
				temp.target = 1;
				temp.priority = input;
				Q.push_back(temp);
			}
			else {
				temp.target = 0;
				temp.priority = input;
				Q.push_back(temp);
			}
		}
		while (!Q.empty()) {
			temp = { Q.front().target,Q.front().priority };//현재 front값 저장
			Q.erase(Q.begin());//큐에서 삭제
			break_flag = 0; // 큐 탐색 시작시 초기화
			for (int i = 0; i < Q.size(); i++) {
				if (Q[i].priority > temp.priority) {
					Q.push_back(temp); //뒤로 보내기
					break_flag = 1;
					break;// 중간에 우선 순위 높은게 있으면 즉시 큐 탐색 중단
				}
			}
			//이 시점에서 break_flag가 0이면 front보다 우선순위 높은 문서는 큐에 없다.
			if (break_flag == 0) {
				if (temp.target == 1) {//front가 내가 알고싶었던 문서이다.
					cout << cnt << '\n';
					break;
				}
				else cnt++;//
			}
		}
		//사용했던 변수,큐를 초기화
		cnt = 1;
		Q.clear();
	}
}

벡터를 큐 처럼 사용했다.

풀이과정

1. 우선순위 값과 내가 알고자 하는 문서의 위치를 기억할 구조체를 선언해서 벡터에 넣어준다.

2. 큐(벡터)의 front값을 저장하고 큐에서 제거한다.

3-1. front값과 front가 제거된 큐의 원소들과 비교해서 front보다 우선순위가 높은 원소가 존재하면 front는 큐의 맨 뒤에 넣고 break_flag를 체크한 후 탐색을 중단한다.

3-2. front 보다 우선순위가 높은 원소가 없으면 break_flag가 0이다. 이 때 저장된 front가 내가 알고자 하는 문서라면 (target = true) 현재까지 출력된 원소들의 개수를 출력 후 반복문 탈출, 아니라면 출력 원소 개수만 ++