https://www.acmicpc.net/problem/1966
문제
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
입력
첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
1. 첫번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자.
2. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
풀이
우선순위 큐
참고 자료: https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
우선순위 큐는 우선순위가 가장 높은 데이터부터 먼저 삭제하는 자료구조이다.
우선순위 큐는 배열, 연결리스트, 힙 등으로 구현이 가능한데, 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.
힙은 완전 이진 트리의 일종으로, 우선순위 큐를 구현하는 데 사용된다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾을 수 있도록 만들어진 자료구조이다.
힙은 일종의 반정렬 상태 (느슨한 정렬 상태)를 유지한다. 다시 말해, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 큰 이진 트리를 유지한다. 힙에서는 중복된 값을 허용한다.
최대 힙(max heap)
"부모 노드의 key 값 >= 자식 노드의 key 값"을 만족하는 완전 이진 트리
최소 힙(min heap)
"부모 노드의 key 값 =< 자식 노드의 key 값"을 만족하는 완전 이진 트리
이 문제에서는 중요도가 높은 문서일수록 가장 먼저 인쇄해야 하므로 최대 힙을 사용하면 된다!
#include<iostream>
#include<queue>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
// 인덱스가 m인 문서가 몇번째로 인쇄되었는지 카운팅하는 변수
int cnt = 0;
queue<pair<int, int>> q;
priority_queue<int> pq; // 기본적으로 최대 힙
for (int i = 0; i < n; i++){
int x;
cin >> x;
q.push({ i, x }); // 인덱스와 중요도
pq.push(x); // 중요도가 높은 순으로
}
while (!q.empty()){
// 큐의 front 원소를 꺼내서
int idx = q.front().first;
int priority = q.front().second;
q.pop();
// 우선순위 큐의 top과 중요도가 일치하면
if (pq.top() == priority){
pq.pop();
cnt++; // 문서 하나 인쇄할 때마다 증가
// 현재 문서의 인덱스가 m인 경우
if (idx == m){
// 몇번째로 인쇄되었는지 출력
cout << cnt << '\n';
break; // 그 다음 테스트 케이스로 넘어가기
}
}
else {
// 중요도가 높지 않으면 큐의 rear에 다시 push
q.push({ idx, priority });
}
}
// 각 테스트 케이스마다 q, pq를 새로 생성하기 때문에
// 컨테이너 초기화는 필요하지 않다.
}
return 0;
}deque
2023-04-19에 다시 풀었는데 deque로도 풀린다.
이 문제를 deque로도 풀 수 있다. C++ deque의 기본 사용법은 이 블로그를 참고하였다. front와 back에서 모두 원소의 삽입, 삭제가 가능한 컨테이너라고 보면 된다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <deque>
using namespace std;
deque<pair<int, int>> dq;
int n, m;
int cnt = 0;
void input() {
cin >> n >> m;
for(int i = 0; i < n; i++){
int x;
cin >> x;
dq.push_back({i, x});
}
}
bool isMaxPriority(int firstPriority) {
// 뒤쪽에 우선순위가 더 높은 게 있는지 검사
for(int j = 1; j < dq.size(); j++){
if(firstPriority < dq[j].second){
// 앞에서 꺼내 뒤에 다시 넣는다.
auto ele = dq.front();
dq.pop_front();
dq.push_back(ele);
return false;
}
}
return true;
}
int popFrontElement() {
int idx = dq.front().first;
dq.pop_front();
cnt++;
return idx;
}
bool equalsIndexOfM(int idx) {
if(idx == m){
cout << cnt << endl;
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
input();
while(!dq.empty()){
if(dq.size() == 1){
dq.pop_front();
cnt++;
cout << cnt << endl;
break;
}
// 첫번째 원소의 우선순위가 가장 높은지 검사
if(isMaxPriority(dq[0].second)){
int idx = popFrontElement();
if(equalsIndexOfM(idx)){
break;
}
}
}
if(!dq.empty()) dq.clear();
cnt = 0;
}
return 0;
}
