[백준] 1966 프린터 큐 - C++

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

---

 

문서 수, 추적할 문서 번호, 문서의 중요도를 입력받고

문서를 중요도순으로 인쇄할 때의 추적하는 문서가 몇 번째로 인쇄되는지 구한다.

---

부분 코드 설명

queue<pair<int, int>> q; //importance, index
queue<int> importance;
int temp[100] = { 0, };

 

사용할 변수들을 선언한다. q는 입력값을 순서대로 저장할 queue이다.

입력값인 중요도와 입력순서(index)를 저장해야 하기 때문에 pair클래스를 사용해 두 값을 저장하도록 했다.

temp 배열에서는 입력받은 중요도 값들을 저장한 후 내림차순 정렬할 수 있도록 한다.

정렬한 temp를 importance에 저장해 중요도가 높은 값부터 하나씩 꺼낼 수 있도록 한다.

 

int n, m;
cin >> n >> m;
for (int j = 0; j < n; j++) {
    cin >> temp[j];
    q.push({ temp[j], j });
}

 

temp 배열에 중요도를 입력받고 q에 중요도와 해당 인덱스를 넣는다.

 

bool compare(int a, int b) {
	return a > b;
}

sort(temp, temp + n, compare);
for (int j = 0; j < n; j++) {
    importance.push(temp[j]);
}

 

temp를 정렬 후 importance에 저장한다

 

if (q.front().first == importance.front()) {
    if (q.front().second == m) {
        cout << cnt + 1 << "\n";
        break;
    }
    else {
        q.pop();
        importance.pop();
        cnt++;
    }
}
else {
    q.push(q.front());
    q.pop();
}

 

q.front().first는 가장 앞에 있는 문서의 중요도를 나타낸다.

importance.front()는 아직 인쇄되지 않은 문서의 중요도 중 가장 높은 중요도를 나타낸다.

이 값이 같다면 해당 문서는 인쇄되어야 한다.

 

q.front().second는 가장 앞에 있는 문서의 번호이므로, 이 값이 추적하려는 문서의 번호인 m과 일치하면, 앞서 출력된 문서의 수를 저장하는 변수 cnt에 1을 더해 출력한다.(앞서 출력된 문서 수 + 자기 자신)

일치하지 않는다면 문서를 인쇄는 하되 원하는 문서가 아니므로 cnt를 증가시킨다.

 

만약 q.front().first와 importance.front()가 같지 않다면 대기열에 있는 문서 중 해당 문서보다 중요도가 높은 문서가 있다는 뜻이다.

이때에는 해당 문서를 대기열의 맨 뒤로 옮긴다.

 

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
bool compare(int a, int b) {
	return a > b;
}
int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		queue<pair<int, int>> q; //importance, index
		queue<int> importance;
		int temp[100] = { 0, };
		int n, m;
		cin >> n >> m;
		for (int j = 0; j < n; j++) {
			cin >> temp[j];
			q.push({ temp[j], j });
		}
		sort(temp, temp + n, compare);
		for (int j = 0; j < n; j++) {
			importance.push(temp[j]);
		}
		int cnt = 0;
		while (!q.empty()) {
			if (q.front().first == importance.front()) {
				if (q.front().second == m) {
					cout << cnt + 1 << "\n";
					break;
				}
				else {
					q.pop();
					importance.pop();
					cnt++;
				}
			}
			else {
				q.push(q.front());
				q.pop();
			}
		}
	}
	return 0;
}

---

 

실버3 인데 이 정도 코드를 쓰는 건

닭 잡는 데에 소 잡는 칼 쓰는 느낌이지만.....

---