[Baekjoon Online Judge] 백준 11286번 절댓값 힙(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11286번 절댓값 힙

(C++, Python)

(글쓴날 : 2020.04.26)

 

---

* Baekjoon Online Judge, 백준 11286번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 11286번 절댓값 힙

---

1) 문제

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

11286번: 절댓값 힙

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

N개만큼 주어지는 정수의 값에 따라 만약, 자연수라면 해당 값을 저장하고, 0이라면 저장되어 있는 수 중 절댓값이 가장 작은 값을 출력 후 제거하는 절댓값 힙을 구현하는 문제입니다.

단, 절댓값이 가장 작은 값이 여러 개일 경우 가장 작은 수를 출력합니다.

 

저의 경우, 우선순위 큐를 적용하였으며, C++과 Python을 사용했습니다.

만약 입력값이 자연수일 시, C++의 경우 pair, Python의 경우 tuple을 사용하여 첫 번째 요소에 절댓값, 두 번째 요소에 원래 값을 저장해 Min Meap 기반의 우선순위 큐에 저장하였고, 입력값이 0일 시 우선순위 큐에 저장된 순서대로 출력하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <cstdlib>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N = 0;
    cin >> N;
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
    int inputValue = 0;
    int tempValue = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> inputValue;
 
        if (!inputValue)
        {
            try
            {
                if (pq.empty())
                    throw 0;
 
                cout << pq.top().second << "\n";
                pq.pop();
            }
            catch (int e)
            {
                cout << e << "\n";
            }
        }
        else
            pq.push(make_pair(abs(inputValue), inputValue));
    }
 
    return 0;
}

---

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
N = int(input())
hq = []
 
for _ in range(N):
    inputValue = int(input())
    
    if not inputValue:
        try:
            print(heapq.heappop(hq)[1])
        except:
            print(0)
    else:
        heapq.heappush(hq, (abs(inputValue), inputValue))

---