문제

BOJ 11286, 절댓값 힙

핵심

• 입력의 크기가 $10^5$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• N개의 수를 배열에 넣는데, 그 수가 0이라면 배열에서 절댓값이 제일 작은 수를 출력하고 배열에서 제거한다. 0이 아니라면 배열에 넣는 작업을 한다. 절댓값이 제일 작은 수가 여러 개 있다면, 제일 작은 수를 출력하고 뽑아낸다.
• 해당 문제는 set, TreeMap을 이용해서 풀 수도 있지만 단순히 최솟값을 구하기에 힙 자료구조인 우선순위 큐를 이용하여 푸는 게 더 적합하다. 시간복잡도는 동일하더라도 전자의 방식이 후자의 방식보다 메모리 사용량이나 연산 과정에서 오버헤드가 크다.
• C++에서 우선순위 큐는 최대 힙을 기준으로 설계되어 정렬 비교함수를 작성할 때 오름차순 정렬이 내림차순이 된다. 즉, 기호를 반대로 두어야 한다. 반면 Java에서는 최소 힙을 기준으로 설계되어 이런 고려를 할 필요가 없다는 점을 유의하자.

개선

코드

시간복잡도

• $O(N\times log_2N)$

C++

#include <iostream>
#include <queue>
using namespace std;

int n;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto comp = [](auto& a, auto& b) {
		int absA = abs(a);
		int absB = abs(b);
		if (absA != absB)
			return absA > absB;
		return a > b;
	};
	priority_queue<int, vector<int>, decltype(comp)> pq(comp);
	cin >> n;
	while (n--) {
		int num;
		cin >> num;
		if (!num) {
			if (pq.empty()) {
				cout << 0 << '\n';
			} else {
				cout << pq.top() << '\n';
				pq.pop();		
			}
		} else 
			pq.push(num);
	}
}

Java

import java.io.*;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
            int absA = Math.abs(a);
            int absB = Math.abs(b);
            if (absA != absB)
                return absA - absB;
            return a - b;
        });
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num == 0) {
                if (pq.isEmpty())
                    bw.write(0 + "\n");
                else
                    bw.write(pq.poll() + "\n");
            } else
                pq.add(num);
        }
        bw.flush();
        bw.close();
        br.close();
    }
}