[BOJ/Java] 11286. 절댓값 힙

[BOJ/Java] 11286. 절댓값 힙

2178번: 미로 탐색

---

문제 해석

이 문제는 절댓값 힙을 구현하는 문제다. 절댓값 힙은 절댓값이 가장 작은 값을 우선으로, 절댓값이 같을 경우 실제 값이 작은 순으로 데이터를 정렬하여 제공하는 자료 구조다. 사용자는 숫자를 하나씩 입력하며, 0을 입력할 경우 절댓값 힙에서 최소 값을 출력하고 제거하도록 요청한다.

풀이 과정

1. 입력 처리: Java의 BufferedReader를 사용하여 입력을 받고, 입력된 숫자의 개수를 저장한다.
2. 절댓값 힙 구현: PriorityQueue를 사용하여 절댓값 힙을 구현한다. 이때, 람다 표현식을 통해 두 숫자를 비교하는 커스텀 정렬을 설정한다. 절댓값이 같은 경우 실제 값에 따라 정렬하며, 그렇지 않으면 절댓값에 따라 정렬한다.
3. 연산 처리: 숫자가 주어질 때마다 해당 숫자가 0인지 아닌지 판별한다. 0일 경우, 힙이 비어 있으면 0을 출력하고, 그렇지 않으면 힙에서 최소값을 꺼내 출력한다. 0이 아닐 경우, 주어진 숫자를 힙에 추가한다.
4. 출력 처리: 결과를 StringBuilder에 저장하여 마지막에 한 번에 출력한다.

코드

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

public class Main {
    int n; // 입력받을 숫자의 개수
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().io();
    }

    private void io() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine()); // 명령의 수 입력 받기
        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a, b) -> {
                    int diff = Math.abs(a) - Math.abs(b); // 절대값 기준으로 비교
                    if(diff == 0) return a-b; // 절대값이 같으면 실제 값으로 비교
                    else return diff;
            });
        
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(br.readLine()); // 명령 입력 받기
            if(x == 0) {
                if(pq.isEmpty()) {
                    sb.append(0).append("\n"); // 힙이 비어 있으면 0 출력
                } else {
                    sb.append(pq.poll()).append("\n"); // 힙에서 최소값 출력
                }
            }     
            else {
                pq.offer(x); // 힙에 값 추가
            }
        }
        
        bw.write(sb.toString()); // 결과 출력
        bw.flush();
        bw.close();
    }
}

시간 복잡도 분석

입력받는 각 숫자에 대해 힙 연산(삽입 또는 삭제)이 수행된다. PriorityQueue는 삽입 및 삭제에 O(log n)의 시간 복잡도를 가지므로, 전체 시간 복잡도는 O(n log n)이 된다.

느낀점

자바의 PriorityQueue를 이용하여 절댓값 힙을 구현하는 방법을 배울 수 있었다. 람다 표현식을 사용하여 간결하게 커스텀 비교 로직을 구현하는 방법도 익힐 수 있어 유익했다. 이러한 데이터 구조를 사용함으로써 복잡한 정렬 조건을 쉽게 처리할 수 있는 장점을 경험할 수 있었다.