[백준/JAVA] 11286번 : 절댓값 힙

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

 

📌 문제 요약 

절댓값 힙은 주어진 정수 배열에서 다음 두 가지 연산을 수행하는 자료구조입니다:

1. 정수 x를 배열에 추가하는 연산.
2. 배열에서 절댓값이 가장 작은 값을 출력하고 제거하는 연산. 절댓값이 같은 값이 여러 개일 경우, 가장 작은 수를 우선하여 출력합니다.

---

[ 오답 노트 ]

❌ 기존 오답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 18
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < N; i++) {
            int a = Integer.parseInt(br.readLine());

            if(a == 0) {
                if(pq.isEmpty()) {
                    sb.append(0).append('\n');
                }else{
                    sb.append(pq.poll()).append('\n');
                }
            }else{
                // [1,-1..]
                // [1,1..]
                pq.add(a);
            }
        }

        System.out.println(sb);

    }
}

 

📌 기존 코드의 문제점

초기 코드에서는 PriorityQueue<Integer>에 단순히 정수를 추가하고 삭제하는 기본 기능만 구현되어 있었으며, 아래와 같은 문제점이 있었습니다.

 

1. 절댓값 기준 정렬이 구현되지 않음

PriorityQueue는 기본적으로 자연 정렬(오름차순 정렬)을 따르기 때문에, 절댓값 기준으로 정렬하지 않습니다.

 

 

2. 절댓값이 같을 때 실제 값이 작은 수를 우선 출력하지 않음

문제에서는 절댓값이 같은 경우 실제 값이 작은 정수를 먼저 출력하도록 요구합니다. 기본 우선순위 큐에서는 이 조건이 만족되지 않았습니다.

 

---

[ 정답 코드 & 올바른 풀이 ]

 

📌 올바른 풀이

1. 절댓값 기준 정렬이 구현되지 않음 문제 해결

PriorityQueue에 절댓값 기준으로 정렬되도록 Comparator를 설정해야 합니다.

 

 

2. 절댓값이 같을 때 실제 값이 작은 수를 우선 출력하지 않음 문제 해결

Comparator에서 절댓값이 같다면 실제 값을 비교하여 작은 값을 우선하도록 설정합니다.

 

 

✅ PriorityQueue를 절댓값 기준으로 정렬되도록 커스텀 Comparator를 설정하여 문제의 요구 사항을 만족하도록 코드를 수정했습니다.

 

 

📌 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 18
        StringBuilder sb = new StringBuilder();

        // 우선순위 큐 : 절댓값 기준으로 정렬, 절댓값이 같으면 실제 값으로 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> {
            int absX = Math.abs(x);
            int absY = Math.abs(y);
            // 절댓값이 같을 경우 ex) 1과 -1일 경우
            if(absX == absY) {
            	// Integer.compare()
                // 첫번째 정수가 두번째 정수보다 작은 경우 '음수값', 같은 경우 '0', 클 경우 '양수값
                return Integer.compare(x, y); // 실제 값이 작은 순대로 정렬  ex) 큐 상태는 [-1,1] 더작은 -1이 우선
            }else{  // 절댓값이 다를 경우 ex) |3| = 3, |-7| = 7
                return Integer.compare(absX, absY); // 큐 상태는 [3, -7] 절댓값 작은 3이 우선
            }
        });


        for(int i = 0; i < N; i++) {
            int a = Integer.parseInt(br.readLine());

            if(a == 0) {
                if(pq.isEmpty()) {
                    sb.append(0).append('\n');
                }else{
                    sb.append(pq.poll()).append('\n');
                }
            }else{
                pq.add(a);
            }
        }

        System.out.println(sb);

    }
}