프로그래머스 - 이중 우선순위 큐

programmers.co.kr/learn/courses/30/lessons/42628#

코딩테스트 연습 - 이중우선순위큐

 

최소 최대를 지울 수 있는 이중 우선순위 큐를 만드는 문제로

최소힙, 최대힙 두개를 만들어서 처리하거나,

multiset 을 이용하여 처리할 수 있다.

(multiset 을 사용한 이유는

1. 앞뒤 양방향에서 접근 할 수 있어야하며,

2. 삽입, 삭제와 동시에 정렬되어야 하기 때문이다.

이런 자료구조를 갖는 것은 red-black tree 기반의 multiset STL 을 사용해야 처리된다)

 

- c++

 

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    multiset<int> ms;
    for (int i = 0; i < operations.size(); ++i) {
        string temp = operations[i];
        char order = temp[0];
        int num = stoi(temp.substr(2, temp.length() - 2));
        
        if (order == 'I') {
            ms.insert(num);
        } else {
            if (!ms.empty()) {
                if (num == 1) {
                    auto iter = ms.end();
                    --iter;
                    ms.erase(iter);
                } else {
                    auto iter = ms.begin();
                    ms.erase(iter);
                }   
            }
        }
        
    }
    
    answer.resize(2, 0);
    if (!ms.empty()) {
        auto iter = ms.begin();
        answer[1] = *iter;
        iter = ms.end();
        --iter;
        answer[0] = *iter;
    }
 
    return answer;
}

 

 

 

 

 

* 이 문제는 백준 7662 이중 우선순위 큐 와 똑같은 문제이다.

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐