[C++] BOJ-1966

 

문제풀이

---

1. 중요도를 저장할 수 있는 priority_queue와 (문서의 처음 위치, 중요도)를 저장할 수 있는 queue를 2개 생성한다.

 

2. 우선순위큐는 가장 높은 우선순위가 top의 위치에 존재하기때문에 우선순위큐의 top과 queue에 있는 요소의 중요도를 체크해서 다르면 큐의 뒤로 넘기고 같으면 pop 한다.

 

3. pop이 될 때마다 count를 해주고 찾고싶은 문서가 pop이 되면 반복문을 종료한다.

 

#include <iostream>
#include <queue>

using namespace std;

int main(){
	
	int T;
	cin >> T;
	
	for(int test = 0; test < T; test++){
		priority_queue<int, vector<int>, less<int> > pq;
		queue<pair <int, int> > q;
		int N,M;
		int importance;
		int cnt = 0;
		
		cin >> N >> M;
		
		for(int i = 0; i<N; i++){
			cin >> importance;
			pq.push(importance);
			q.push(make_pair(i,importance));
		}
		
		while(1){
			if(q.front().first == M && pq.top() == q.front().second){
				cout << cnt+1 << "\n";
				break;
			}
			
			if(q.front().second != pq.top()){
				int tmp_x = q.front().first;
				int tmp_y = q.front().second;
				q.pop();
				q.push(make_pair(tmp_x,tmp_y));
			}else if(q.front().second == pq.top()){
				q.pop();
				pq.pop();
				cnt++;
			}
		}
	}
	return 0;	
}