[Programmers]#Level3_이중 우선 큐, set, multiset

 

[Programmers 알고리즘, C++]#Level 3_이중 우선 큐

 

Programmers 알고리즘 문제 풀이, Level3_이중 우선 큐

C++의 STL에서 제공하는 multiset 컨테이너를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

#2. 풀이

1. set

[Basic C++] #29_Set, STL 컨테이너

 

• [정의] : set은 C++의 STL에서 제공하는 연관 컨테이너입니다. 노드 기반의 컨테이너이며, 균형 이진트리(레드-블랙 트리)로 구현되어 있습니다. set은 Key 값을 원소로 이루어진 집합이며, 중복을 허용하지 않고 항상 정렬된 상태를 유지합니다.

 

2. multiset

• [정의] : multiset은 C++의 STL에서 제공하는 연관 컨테이너입니다. 노드 기반의 컨테이너이며, 균형 이진트리(레드-블랙 트리)로 구현되어 있습니다. multiset은 Key값을 원소로 이루어진 집합이며, 중복을 허용하고 항상 정렬된 상태를 유지합니다.

 

3. 레드-블랙 트리(균형 이진 트리)

[자료구조]#5_트리

 

3. 최솟값과 최댓값

1. 먼저, "multiset"을 선언합니다. " 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다. "라는 지문의 설명에 따라서, 중복을 허용하며 내부적으로 정렬 상태를 항상 유지하는 multiset 컨테이너를 활용합니다. 
2. "D 1"이면, multiset 컨테이너의 첫 번째 항목을 삭제하고, "D -1"이면, multiset 컨테이너의 마지막 항목을 삭제해 줍니다.

 

#3. 코드

#include <string>
#include <vector>
#include <set>
#include <sstream>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    // #1. multiset 선언 및 오름차순 정렬
    multiset<int, less<int>> ms;
    
    char c; int n;
    for(int i=0; i<(int)operations.size(); i++)
    {
        stringstream ss(operations[i]);
        ss >> c;
        ss >> n;
        
        if(c=='I')
        {
            ms.insert(n);
        }
        else
        {
            if(n == 1 and !ms.empty())
            {
                ms.erase(--ms.end());
            }
            else if(n == -1 and !ms.empty())
            {
                ms.erase(ms.begin());
            }
        }
    }
    
    if(ms.empty())
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
        answer.push_back(*(--ms.end()));
        answer.push_back(*(ms.begin()));
    }
    
    return answer;
}