백준 7662 이중 우선순위 큐

백준 7662 이중 우선순위 큐

링크 : https://www.acmicpc.net/problem/7662

문제 요약

◆ I N : N을 삽입
◆ D 1 : 최댓값을 삭제
◆ D -1 : 최솟값을 삭제
◆ k번의 연산후 남아있는 최댓값과 최솟값을 출력

키 포인트

◆ I N 명령어가 입력된 경우 N을 삽입 후 정렬을 통해 최댓값은 맨 뒤에, 최솟값은 맨 앞에 위치하도록 한다.

◆ D 명령어가 입력된 경우 맨 앞 또는 맨 뒤에서 값을 제거해준다. 최종적으로 맨 앞과 맨 뒤에 있는 수를 출력해주면 된다.

시행착오

1. vector에 삽입후 stl의 sort 함수를 통해 정렬을 시도
   = sort의 시간 복잡도가 O(NlogN)이고 k ≤ 1,000,000 이므로 당연히 시간초과

2. 삽입시 자동으로 정렬을 해주는 set 컨테이너로 재시도
   = '중복된 값'이 존재할 수 있다는 문제의 조건을 간과 (set은 중복된 값 허용x)

3. multiset을 이용해 재시도 -> 해결

코드

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tc;
	cin >> tc;

	for (int i = 0; i < tc; i++) {
		int n;
		cin >> n;
		multiset<ll> s;
		for (int j = 0; j < n; j++) {
			char op;
			ll num;
			cin >> op >> num;
			if (op == 'I') s.insert(num);
			else if (op == 'D') {
				if (!s.empty()) {
					if (num == 1) {
						auto it = s.end();
						s.erase(--it);
					}
					else if (num == -1) s.erase(s.begin());
				}
			}
		}
		if (!s.empty()) {
			auto it = s.end();
			cout << *(--it) << ' ' << *(s.begin()) << '\n';
		}
		else cout << "EMPTY\n";
	}
}

추가

◆ set의 사용이 미숙해 끝 원소를 어떻게 제거할지 잠시 고민했다. 복습하자.

◆ 이 문제는 위와 같은 방식 외에도 우선순위큐나 Heap을 이용한 풀이가 가능하다. 다음번에는 다른 방법으로도 풀어보자.