이중우선위 큐 (Level 3)
문제
코딩테스트 연습 - 이중우선순위큐
programmers.co.kr
접근법
보통 우선순위큐는 항상 가장 우선순위가 높은 원소를 뽑기 위해서 사용한다. 이런 우선순위 큐에서는 아쉽게도 가장 우선순위가 낮은 원소를 뽑거나 알 수는 없다. 이 문제에서 요구하는 바는 가장 우선순위가 높은 원소를 뽑을 수도, 가장 우선순위가 낮은 원소를 뽑을 수도 있는 이중 우선순위 큐를 구현하는 것이다.
이중 우선순위 큐를 구현하기 위한 자료구조는 반드시 우선순위를 기준으로 정렬되어 있어야한다. 이때 사용하기 좋은 자료구조는 균형 이진트리이다. 물론 배열이나 연결 리스트로도 구현할 수는 있다. 다만 배열과 연결 리스트를 항상 정렬된 상태로 유지하기 위해서는 데이터를 삽입할 때 삽입될 위치를 탐색하는 과정이 필요하다. 이때 배열이나 연결 리스트의 탐색 시간은 최악의 경우 \(O(n)\)이기 때문에 \(n\) 개의 데이터를 삽입하기 위해서는 최악의 경우 \(O(n^2)\) 만큼의 시간이 필요하다. 하지만 균형 잡힌 이진트리를 사용할 경우 탐색과정에 \(O(logn)\)만큼의 시간이 필요하기 때문에 \(n\) 개의 데이터를 삽입하기 위해서 최악의 경우에도\(O(nlogn)\)의 시간만 요구된다.
그 외 가장 작은값 혹은 가장 큰 값을 삭제하는데 걸리는 시간은 배열과 리스트, 균형 잡힌 이진트리 모두 1회 만에 수행할 수 있다. (다만 배열의 경우 배열의 앞쪽 원소를 삭제하기 위해서는 deque를 사용해야 하고, 메모리 동적 할당에 따른 시간이 더 소요될 수 있다.)
이번 문제를 풀기 위해서 C++의 set을 이용했다. set은 균형잡힌 이진트리로 이루어진 자료구조이며, 중복 값을 허용하지 않는다는 특징을 가지고 있다. set은 기본적으로 다음과 같은 구조를 가지고 있다.
구현
내부에서는 set을 활용하고 문제에서 요구하는 기능들(원소 삽입, 가장 큰값 삭제 및 조회, 가장 작은 값 삭제 및 조회) 인터페이스로 제공하는 이중우선순위큐 클래스를 제작하여 사용하였다.
#include <string>
#include <vector>
#include <sstream>
#include <set>
using namespace std;
class DPriority_Queue
{
public:
// set에 데이터 입력
void insert(int n)
{
mSet.insert(n);
}
// 가장 작은 값 삭제
void pop_min()
{
if(!mSet.empty())
mSet.erase(mSet.begin());
}
// 가장 큰 값 삭제
void pop_max()
{
if(!mSet.empty())
mSet.erase(--mSet.end());
}
// 가장 큰 값 조회
int max()
{
if(!mSet.empty())
return *(--mSet.end());
else
return 0;
}
// 가장 작은값 조회
int min()
{
if(!mSet.empty())
return *mSet.begin();
else
return 0;
}
private:
set<int> mSet;
};
vector<int> solution(vector<string> operations) {
vector<int> answer;
DPriority_Queue Dpq;
stringstream ss;
char command;
int data;
for(string operation : operations)
{
// 입력 문자열을 문자열스트림으로 변환 후 데이터 입력받음
ss.str(operation);
ss >> command;
ss >> data;
ss.clear();
if(command == 'I') // 데이터 입력
Dpq.insert(data);
else if(data == 1)
Dpq.pop_max(); // 가장 큰 값 삭제
else
Dpq.pop_min(); // 가장 작은 값 삭제
}
answer = {Dpq.max(), Dpq.min()}; // 가장 큰 값, 가장 작은 값 조회 후 반환
return answer;
}