백준 1966 : 프린터 큐 _ C++ , +) 우선순위 큐 pair compare

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

1966번: 프린터 큐

#시뮬레이션 #큐 #silver3

 

회고

 

✔ 알고리즘 접근 방식

처음에는 우선순위 큐 한개에 pair로 인덱스 정보와 중요도를 함께 저장 해 줬는데 인덱스도 같이 정렬되어버려서 그 부분은 어떻게 처리를 해야하나 장시간 고민을 했다. (cmp함수도 만들어서 해당 부분을 어떻게 해결해보려 했는데 불가능했다..ㅠ) 

고민을 아무리 해봐도 딱히 뾰족한 수가 떠오르지 않아서 다른 사람들은 어떻게 풀었는지 찾아봤다.

큐와 우선순위 큐 두개를 이용하여 푼 풀이를 봤고, 나 역시 큐를 두개 사용하기로 결정했다.

 

✔ 큐 두개

우선순위 큐는 중요도를 높은 순으로 정렬해줬고, 큐에는 처음 상태 그대로 저장해줬다.

큐에서 원소를 한개씩 빼보면서 우선순위 큐의 첫번째 원소와 일치하면 카운팅을 해줬고, 일치할 때 문제에서 묻는 인덱스 위치와 해당 인덱스 위치가 동일 할 경우 카운팅 된 숫자를 출력하고 해당 테스트 케이스는 종료해줬다.

 

 

cf) 우선순위 큐 compare 적용법 (자주 헷갈려해서..!)

struct cmp {
	bool operator()(pair<int, int>a, pair<int, int>b) {
		if (a.first == b.first) return a.second > b.second;
		return a.first > b.first;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

 

코드

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

int t, n, place;

int main() {
	cin >> t;
	while (t--) {
		priority_queue<int> pq;
		queue<pair<int, int>> q;

		cin >> n >> place;
		int pri;
		for (int i = 0; i < n; i++) {
			cin >> pri;
			q.push({ pri,i });
			pq.push(pri);
		}
		int cnt = 0;
		while (!pq.empty()) {
			int val = q.front().first;
			int index = q.front().second;
			q.pop();
			if (pq.top() == val) {
				pq.pop();
				cnt++;
				if (index == place) {
					cout << cnt << '\n';
					break;
				}
			}

			q.push({ val, index });
		}
	}
	return 0;
}