[백준/알고리즘] 7662번 이중 우선순위 큐 (골드 5)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 7662번

 

우선순위가 가장 큰 데이터와 가장 작은 데이터를 모두 삭제할 수 있는 기능을 가진 이중 우선순위 큐를 구현하시오.

 

풀이 알고리즘 : STL-MAP (트리)

 

입력이 들어오면, 해당 데이터의 우선순위(크기)에 따라서 위치를 조정해줘야 하므로,배열을 이용하여 입력때마다 정렬을 하거나 하는 방법은 시간초과가 날 수 있다.

 

그래서 STL의 MAP 컨테이너를 사용할 것이다.

 

MAP은 key와 value로 구성되어, key값을 통해 value로 빠르게 접근할 수 있는 컨테이너이다.

 

그런데 왜 사용하냐면, MAP은 입력받을 때 마다, 해당 데이터를 적절한 위치에 위치시키기 때문에 항상 정렬이 되어있다.즉 Map.begin()이 가장 작은 값이고, 그대로 순회를 하면 오름차순으로 값이 커지게 된다.

 

그래서 map<int, int>를 선언하고, key값을 데이터의 값, value값을 해당 데이터의 개수로 정의하여 선언하였다.

 

그래서 MAP 내부에 입력받은 데이터가 존재하지 않으면 (data, 1)을 입력하고, 존재한다면 개수를 1 증가시키는 방법을 사용하였다.

 

아래는 제출코드이다.

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// int pair 간단히
#define pii pair<int, int>
#define mp(X, Y) make_pair(X, Y)

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

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

	int tc;
	cin >> tc;

	while(tc--) {
		map<int, int> checker;
		int n, qsize = 0;
		cin >> n;

		while(n--) {
			char order;
			int data;
			cin >> order >> data;

			if(order == 'I') {
				map<int, int>::iterator it = checker.find(data);
				if(it != checker.end()) {
					(*it).second++;
				} else {
					checker.insert(mp(data, 1));
				}
				qsize++;
			} else {
				if(qsize == 0) continue;
				else if(data == -1) {
					map<int, int>::iterator it = checker.begin();
					if(it->second == 1) {
						checker.erase(it->first);
					} else {
						(*it).second--;
					}
				} else {
					map<int, int>::reverse_iterator it = checker.rbegin();
					if(it->second == 1) {
						checker.erase(it->first);
					} else {
						(*it).second--;
					}
				}
				qsize--;
			}
		}

		if(qsize) {
			cout << checker.rbegin()->first << " " << checker.begin()->first << "\n";
		} else {
			cout << "EMPTY\n";
		}
	}

	return 0;
}