백준 1966 풀이

링크텍스트

큐를 활용한 문제였다.
하지만 c++ stl에서 제공해주는 큐에서는 iterator를 지원해주지 않아 deque를 썼다.

문제를 풀 때 제일 먼저 생각한 것은 큐에서 최대 우선순위와 최소 우선순위를 찾아야한다는 것이다.

또한 큐에 저장할 때 pair(우선순위, index)형태로 저장했다.

큐를 탐색하면서 최대, 최소값을 찾았고 큐의 앞에서부터 하나씩 꺼내 이 값이 맥스면 큐에서 제외하고 count를 증가시킨다. 이후 현재 꺼낸 값의 인덱스가 찾고자하는 위치의 문서와 일치한다면 그 때까지의 count값이 정답이 된다. 일치하지 않을 경우 꺼낸 pair를 다시 큐에 집어 넣는다.

min==max은 남은 문서의 우선순위가 동일하다는 것이기때문에 위와같은 방식으로는 구하기 어렵다. 그래서 기존의 반복문을 빠져나와 남은 큐를 탐색하면서 찾는 문서와 같은 인덱스를 가진 문서가 큐에 남아있는지 검사를 하여 있다면 정답으로 한다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
using namespace std;

int t;
int n;
int m;
long long arr[1001];

int findMin(deque<pair<int, int>> q) {
	int min = 10;
	for (int i = 0; i < q.size(); i++) {
		int tmp = q.at(i).first;
		if (tmp <= min) {
			min = tmp;
		}
	}
	return min;
}

int findMax(deque<pair<int, int>> q) {
	int max = 0;
	for (int i = 0; i < q.size(); i++) {
		int tmp = q.at(i).first;
		if (tmp >= max) {
			max = tmp;
		}
	}
	return max;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> t;
	for (int k = 0; k < t; k++) {
		deque<pair<int, int>> v;
		int answer = 0;
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			int tmp;
			cin >> tmp;
			pair<int, int> p(tmp, i);
			v.push_back(p);
		}
		int min = findMin(v);
		int max = findMax(v);
		int count = 0;
		while (true) {
			if (min == max)
				break;
			pair<int, int> tmp = v.front();
			v.pop_front();
			if (tmp.first == max) {
				count++;
				max = findMax(v);
				if (tmp.second == m) {
					answer = count;
				}
			}
			else {
				v.push_back(tmp);
			}
		}
		for (int i = 0; i < v.size(); i++) {
			count++;
			int tmp = v.at(i).second;
			if (tmp == m) {
				answer = count;
				break;
			}
		}
		cout << answer << '\n';
	}
	return 0;
}