문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
입력
첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
예제
문제 정의
나는 이 문제를 deque를 이용해서 풀었는데 다른 사람의 풀이를 보니 풀이 방법이 여러가지였다.
먼저 내가 푼 방법을 소개하겠다.
문제 입력에서 중요도가 같은 문서가 여러 개 있을 수 있다고 했기 때문에, 문서의 우선순위만을 저장하기엔 무리가 있다. 따라서 궁금한 문서의 index와 궁금한 문서의 우선순위 값을 pair<int, int>로 묶어 deque에 저장했다.
그 후 반복문을 돌며 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 있을 경우 현재 문서를 deque의 뒤에 삽입한 후 원래 있던 값을 삭제했다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 없을 경우는 문서를 찾는데 걸린 횟수(cnt)를 +1해주고 현재 문서가 찾는 문서인지 확인했다.
현재 문서가 찾는 문서가 아닐 경우엔 dq의 맨 앞의 원소를 삭제하는 식으로 진행했다.
deque가 empty일 경우 반복문을 빠져나오도록 설계했다.
코드는 다음과 같다.
#include<deque>
#include<iostream>
using namespace std;
int t, n, m, prio;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
for (int i = 0; i < t; i++) {
cin >> n >> m;
deque<pair<int, int>> dq;
for (int j = 0; j < n; j++) {
cin >> prio;
dq.push_back({j, prio});
}
pair<int, int> fi = make_pair(m, dq[m].second);
int cnt = 0;
while (true)
{
if (dq.empty()) {
break;
}
pair<int, int> tmp = dq.front();
int flag = 0;
for (int k = 1; k < dq.size(); k++) {
if (tmp.second < dq[k].second) {
flag = 1;
break;
}
}
if (flag) {
dq.push_back(tmp);
dq.pop_front();
} else {
cnt++;
if (tmp == fi) {
cout << cnt << "\n";
break;
}
dq.pop_front();
}
}
}
return 0;
}🔥 우선순위 큐를 이용하는 방법
우선순위 큐를 써본 적이 없는데 다른 사람의 경우 우선순위 큐로 풀이를 많이 했다.
우선 순위 큐
우선순위 큐(Priority Queue, PQ)는 큐의 한 종류로, 각 원소가 우선순위(priority)를 가지고 있고, 큐에서 가장 우선순위가 높은 원소가 먼저 꺼내지는 자료 구조이다. 즉, FIFO(First-In-First-Out) 방식이 아닌, 우선순위가 높은 원소부터 처리되는 방식이다.
우선순위 큐는 일반적으로 힙(heap)을 사용하여 구현된다. 힙은 완전 이진 트리 형태로, 부모 노드가 자식 노드보다 우선순위가 높은 특성을 가진다. 우선순위 큐에서는 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 사용할 수 있다.
c++의 priority_queue<자료형>의 default는 최대힙이다.
기본적으로 우선순위 큐에 원소를 push 할때마다 내부적으로 O(logN) 시간으로 우선순위에 따라 내림차순으로 자동 정렬되어 저장된다.
- 우선순위 큐 (default. 최대힙)
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(10);
pq.push(20);
pq.push(15);
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
// 출력: 25 15 10
return 0;
}- 우선순위 큐에서 최소힙을 사용하고 싶은 경우
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 최소 힙 (오름차순 정렬)
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(10);
pq.push(20);
pq.push(15);
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
// 출력: 10 15 25
return 0;
}우선순위 큐를 이용한 풀이
#include<iostream>
#include<queue>
using namespace std;
int t, n, m, prio;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
for (int i = 0; i < t; i++) {
queue<pair<int, int>> q;
priority_queue<int> pq;
int cnt = 0;
cin >> n >> m;
for (int j = 0; j < n; j++) {
cin >> prio;
q.push({j, prio});
pq.push(prio);
}
while (!q.empty())
{
int index = q.front().first;
int value = q.front().second;
q.pop();
if (pq.top() == value) {
pq.pop();
++cnt;
if (index == m) {
cout << cnt << "\n";
break;
}
} else
q.push({index, value});
}
}
return 0;
}