[백준] 11286번 절대값 힙

 

 

문제

소스코드

 

#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
 
constexpr int POP = 0;
using priority_queue = std::priority_queue<int, std::vector<int>, std::greater<int>>;
using MinusCounter = std::pair<int, int>;
 
// Zero number is pop 
// other numbers is push
 
int main() {
    priority_queue heap;
    std::vector<int> printVector;
    std::map<int,int> map;
    int total{};
 
    std::cin >> total;
    for (int i = 0; i < total; ++i) {
        int value{};
        std::cin >> value;
 
        if (value == POP) {
            // if Queue is Empty print Zero
            if (heap.empty() == true) {
                printVector.emplace_back(0);
            }
            else {
                auto TopVaule = heap.top();
                auto iter = map.find(TopVaule);
 
                if (iter != map.end() && iter->second > 0) {
                    iter->second--;
                    TopVaule *= -1;
                }
 
                printVector.emplace_back(TopVaule);
                heap.pop();
            }
 
        }
        else {
            //0보다 작다면 map에 값을 저장하자
            if (value < 0) {
                auto iter = map.find(abs(value));
                //찾아보고 있다면 증가
                if (iter != map.end()) {
                    iter->second++;
                }
                //없으니까 새로만들기
                else {
                    map.emplace(MinusCounter(abs(value), 1));
                }
                heap.push(abs(value));
            }
            else {
                heap.push(value);
            }
        }
    }
 
    for (const auto& i : printVector) { 
        std::cout << i << "\n";
    }
 
}

 

후기

 

이 문제를 해결하기 위한 키워드는 우선순위 큐이다.

 

먼저 이 문제는 기존 최소 힙에서 조금 변형된 절대 값을 출력하는 힙이다. 이 문제를 풀기 위해서

MinusCounter라는 Map 컨테이너 변수를 하나 추가했다. 이 변수의 역할은 기존 -1, -2와 같은 음수 값이 우선순위 큐에 들어갈 때 MinusCounter을 증가시켜서 값을 저장하고 pop 할 때 이 counter가 있다면 기존의 값이 음수 값이라는 걸 판단할 수 있기 때문에 이렇게 구성해서 출력할 때 부호를 바꾸게 문제를 풀었다.

 

출처 및 레퍼런스

문제 링크: www.acmicpc.net/problem/11286

 

관련 글

[자료구조 알고리즘/큐(Queue)와 스택(Stack)] - 우선 순위 큐(Priority Queue)

[온라인 코딩/힙(Heap)] - [백준] 1927번 최소 힙

[온라인 코딩/힙(Heap)] - [백준] 11279번 최대 힙