[이중우선순위큐/LV3/Python3, C++]

이중 우선순위 큐 LV3

 

문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
I 숫자큐에 주어진 숫자를 삽입합니다.
D 1 큐에서 최댓값을 삭제합니다.
D -1 큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해 주세요.

제한사항
operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
operations의 원소는 큐가 수행할 연산을 나타냅니다. 원소는 “명령어 데이터” 형식으로 주어집니다.
최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.




제한 조건
bridge_length는 1 이상 10,000 이하입니다.
weight는 1 이상 10,000 이하입니다.
truck_weights의 길이는 1 이상 10,000 이하입니다.
모든 트럭의 무게는 1 이상 weight 이하입니다.


입출력 예

operations	return
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0, 0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333, -45]

 

알고리즘 고득점 Kit의 힙 문제 중 하나이다.

 

해시 맵을 사용 하여서 값과 index를 저장하였다.

pop을 할 때 값의 index를 -1로 변경하여서 이미 없어진 수라는 것을 확인하게 하였다.

pop시 index가 같은 경우에만 정상적인 삭제 명령을 진행했다고 판단했다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct val
{
    int index;
    int value;
    val(int _index, int _value) : index(_index), value(_value) {}
};

struct less_compare
{
    bool operator()(const val a, const val b)
    {
        return a.value < b.value;
    }
};
struct greater_compare
{
    bool operator()(const val a, const val b)
    {
        return a.value > b.value;
    }
};


vector<int> solution(vector<string> operations) {
    unordered_map<int, int> maps;
    
    priority_queue<val, deque<val>, less_compare> max_pq; // 최대 힙
    priority_queue<val, deque<val>, greater_compare> min_pq; // 최소 힙
    
    int index = 0;
    for(auto string_data : operations)
    {
        char op = string_data[0];
        int value = stoi(string_data.substr(2));
        
        if(op == 'I')
        {
            maps[value] = index;
            max_pq.push(val(index, value));
            min_pq.push(val(index, value++));
            continue;
        }
        if(value > 0)
        {
            while (!max_pq.empty() && maps[max_pq.top().value] != max_pq.top().index)
            {
                maps[max_pq.top().value] = -1;
                max_pq.pop();
            }
                
            if(!max_pq.empty())
            {
                maps[max_pq.top().value] = -1;
                max_pq.pop();
            }
        }
        else
        {
            while (!min_pq.empty() && maps[min_pq.top().value] != min_pq.top().index)
            {
                maps[min_pq.top().value] = -1;
                min_pq.pop();
            }
            if(!min_pq.empty())
            {
                maps[min_pq.top().value] = -1;
                min_pq.pop();
            }
        }
    }
    
    
    
    vector<int> answer;
    while (!min_pq.empty() && maps[min_pq.top().value] != min_pq.top().index)
        min_pq.pop();
    while (!max_pq.empty() && maps[max_pq.top().value] != max_pq.top().index)
        max_pq.pop();
    
    answer.push_back(max_pq.empty() ? 0 : max_pq.top().value);
    answer.push_back(min_pq.empty() ? 0 : min_pq.top().value);
    
    return answer;
}

 

 

import heapq

def solution(operations):
    dic = {}
    min_q = []
    max_q = []
    
    for i in range(len(operations)):
        operator, num = operations[i].split()
        num = int(num)
        
        if operator == "I":
            dic[num] = i
            heapq.heappush(min_q, (num, i))
            heapq.heappush(max_q, (-num, i))
            continue
        
        if num > 0:
            while max_q:
                val, index = heapq.heappop(max_q)
                if dic[-val] != index: continue
                dic[-val] = -1
                break
        else:
            while min_q:
                val, index = heapq.heappop(min_q)
                if dic[val] != index: continue
                dic[val] = -1
                break
    
    while max_q:
        val, index = max_q[0]
        if dic[-val] == index: break
        heapq.heappop(max_q)
    while min_q:
        val, index = min_q[0]
        if dic[val] == index: break
        heapq.heappop(min_q)
    
    if min_q: return [-max_q[0][0], min_q[0][0]]
    else: return [0, 0]

 

 

---