[Baekjoon Online Judge] 11286. 절댓값 힙 (C++, Java)

https://www.acmicpc.net/problem/11286

설명

 

---

핵심

대놓고 힙을 사용하라고 했기 때문에 따로 생각할 요소는 없다.

힙은 라이브러리에 포함된 우선순위 큐를 사용하면 되고
주어진 조건에 맞게 비교 함수를 구현하는 방법만 학습하면 된다.

---

구현

Code (Java)

비교 함수를 람다로 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            if (Math.abs(o1) == Math.abs(o2)) {
                return o1 - o2;
            } else {
                return Math.abs(o1) - Math.abs(o2);
            }
        });

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num == 0) {
                sb.append(pq.isEmpty() ? 0 : pq.poll()).append('\n');
            } else {
                pq.offer(num);
            }
        }

        System.out.println(sb);
    }
}

Code (C++)

#include <bits/stdc++.h>
using namespace std;

int N;

struct cmp {
	bool operator()(int a, int b) {
		if (abs(a) != abs(b)) return abs(a) > abs(b);
		return a > b;
	}
};

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	priority_queue<int, vector<int>, cmp> pq;

	cin >> N;
	int x;
	for (int i = 0; i < N; i++) {
		cin >> x;
		if (x != 0) pq.push(x);
		else if (pq.empty())
			cout << 0 << '\n';
		else {
			cout << pq.top() << '\n';
			pq.pop();
		}
	}
}