문제

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

풀이

시간초과

deque

#include <iostream> 
#include <vector> 
#include <string>
#include <algorithm> 
#include <queue> 
#include <deque> 
using namespace std;

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

	int t; 
	cin >> t; 

	while(t--){
		deque<int> dq;

		int k; 
		cin >> k;
		
		for(int i = 0; i < k; i++){ // 최대 100만 
			char cmd;
			int num; 
			cin >> cmd >> num;

			if(cmd == 'I'){ // 원소 삽입 후 정렬
				dq.push_back(num); 
				sort(dq.begin(), dq.end()); 
			}else{
				if(num == -1){ 
					if(dq.empty()) continue;
					dq.pop_front(); 
				}else{ 
					if(dq.empty()) continue;
					dq.pop_back(); 
				}
			}
		}

		if(!dq.empty()) {
			// 최댓값, 최솟값 출력 (사이즈가 1이면 두개가 동일)
			cout << dq.back() << " " << dq.front() << endl;
		}else{
			cout << "EMPTY\n"; 
		}
	}
	
	return 0;
}

deque는 컨테이너의 앞, 뒤에서 모두 삽입, 삭제 연산을 수행할 수 있다. 하지만, 자동으로 정렬되지는 않기 때문에 삽입할 때마다 정렬하는 식으로 구현했더니 시간초과가 발생했다.

priority_queue

우선순위 큐는 큐의 일종이므로, front에서는 삭제, back에서는 삽입 연산이 이뤄진다. 그리고 우선순위 큐에서 front는 top이라고 불리는데, top에는 최대 힙이면 최댓값, 최소 힙이면 최솟값이 위치한다.

그래서 아래와 같이 최대 힙과 최소 힙을 전환하면서 풀었는데 역시나 시간초과 발생..

#include <iostream> 
#include <vector> 
#include <string>
#include <algorithm> 
#include <queue> 
#include <deque> 
using namespace std;

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

	int t; 
	cin >> t; 

	while(t--){
		priority_queue<int> pq; // 기본적으로 최대 힙 

		int k; 
		cin >> k;
		
		for(int i = 0; i < k; i++){ // 최대 100만 
			char cmd;
			int num;
			cin >> cmd >> num;

			if(cmd == 'I'){ // 원소 삽입 
				pq.push(num);
			}else{
				if(num == -1){ 
					if(pq.empty()) continue;

					// 최소 힙으로 변환 후 top 삭제
					priority_queue<int, vector<int>, greater<int>> minHeap;
					while(!pq.empty()){
						minHeap.push(pq.top()); 
						pq.pop(); 
					}
					minHeap.pop();

					// 다시 최대 힙으로 변환해보자. 
					while(!minHeap.empty()){
						pq.push(minHeap.top()); 
						minHeap.pop();
					} 
				}else{ 
					if(pq.empty()) continue;

					// 최대 힙의 top 삭제 
					pq.pop(); 
				}
			}
		}

		if(!pq.empty()) {
			if(pq.size() == 1) {
				cout << pq.top() << " " << pq.top() << endl;
				return 0; 
			}

			cout << pq.top() << " "; // 최댓값 
			while(!pq.empty()){ 
				if(pq.size() == 1){
					cout << pq.top() << endl; // 최솟값 
					break; 
				}
				pq.pop(); 
			}
		}else{
			cout << "EMPTY\n"; 
		}
	}
	
	return 0;
}

multiset

https://donggoolosori.github.io/2020/09/24/boj-7662/

위의 블로그를 참고하여, multiset 자료구조를 이용해서 풀 수 있다는 걸 알게 되었다! priority_queue는 자동 정렬되긴 하지만, top 위치의 원소에만 접근할 수 있다는 게 단점이었다. multiset은 key가 중복될 수 있는 set으로, 자동 정렬되면서도 이터레이터를 이용하여 front, back 위치에 모두 접근할 수 있다. 그리고 erase 함수에서 삭제할 원소의 위치를 지정할 수 있다. (값을 지정하면, 해당 값을 가진 원소를 모두 삭제한다. 위치를 지정하면, 해당 위치의 원소만 삭제한다.)

#include <iostream> 
#include <vector> 
#include <string>
#include <algorithm> 
#include <queue> 
#include <deque> 
#include <set> 
using namespace std;

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

	int t; 
	cin >> t; 

	while(t--){
		multiset<int> ms; // 오름차순 정렬 
		
		int k; 
		cin >> k;
		
		for(int i = 0; i < k; i++){ // 최대 100만 
			char cmd;
			int num;
			cin >> cmd >> num;

			if(cmd == 'I'){ // 원소 삽입
				ms.insert(num);
			}else{ 
				if(!ms.empty() && num == -1){ 
					// 최솟값 삭제 
					ms.erase(ms.begin()); 
				}
				
				if(!ms.empty() && num == 1){
					// 최댓값 삭제 
					auto it = ms.end(); // 마지막 원소 바로 다음 위치 
					ms.erase(--it); 
				}
			}
		}

		if(!ms.empty()) {
			auto it = ms.end(); it--; 
			cout << *it << " " << *ms.begin() << endl; 
		}else{
			cout << "EMPTY\n"; 
		}
	}
	
	return 0;
}

이 문제를 통해 컨테이너 앞, 뒤에서의 삭제 연산과 원소의 자동 정렬이 필요한 상황에서는 multiset 자료구조를 사용할 수 있다는 걸 배웠다.

• LIFO: stack, FIFO: queue
• 컨테이너의 앞, 뒤에서 삽입, 삭제 연산이 필요하면? deque
• 원소의 자동 정렬과 top에 대한 접근만 필요하면? priority_queue
• 원소의 중복 제거와 자동 정렬이 필요하면? set
• set과 동일한데 원소의 중복을 허용하면? multiset (원소 접근 및 삭제 연산이 자유로움.)

이 외에도 C++ STL의 컨테이너 종류에 대해 자세히 알고 싶으면 이 링크를 참고하자!