[백준] 절댓값 힙 JAVA

반응형

728x90

[백준] 절댓값 힙

---

접근

• 우선순위 큐

---

풀이

힙을 구현하는데 절댓값을 사용하는 힙의 입출력을 구현하는 문제이다. 단순히 저번 최소 힙 문제에서 절댓값을 사용하고 절댓값이 같을 경우 숫자가 더 작은 수를 루트로 사용하게 된다. 저번 문제 코드에 한 부분만 수정을 하면 되는 문제이다.

2024.08.29 - [알고리즘/코딩테스트-백준] - [백준] 최소 힙 JAVA

[백준] 최소 힙 JAVA

달라지는 부분은 힙으로 사용하는 우선순위 큐의 우선순위를 변경해주기만 하면 해결된다.

PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> {
    int absCompare = Integer.compare(Math.abs(a), Math.abs(b));
    if (absCompare != 0) {
        return absCompare;
    } else {
        return Integer.compare(a, b);
    }
});

우선순위 큐의 우선순위를 변경할 때 Comparator를 구현하여 정렬 기준으로 사용한 뒤 큐를 생성해 주면 된다. 객체나 정렬 기준이 복잡한 경우 Comparator 인터페이스를 구현하여 사용하는게 편한데 일반 정수가 들어가는 큐에다 정렬 조건도 간단하기 때문에 이런 경우 주로 생성자에 람다식으로 구현하는 편이다.

 

정렬 내용으로는 Integer의 compare 메서드를 통해 절댓값을 비교해준다. 절댓값은 Math의 abs 메서드를 통해 사용하고 compare 메서드는 단순히 a-b를 통해 값의 차를 반환한다. 반환값이 음수라면 두 번째 값이 더 크다는 의미이고 양수라면 첫 번째 값이, 0이라면 두 값이 동일하다는 뜻이다. 절댓값을 먼저 비교하여 같다면 기본 정수값으로 비교하여 정렬을 해주게 된다.

---

전체 코드

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> queue = new PriorityQueue<>((a,b) -> {
            int absCompare = Integer.compare(Math.abs(a), Math.abs(b));
            if (absCompare != 0) {
                return absCompare;
            } else {
                return Integer.compare(a, b);
            }
        });

        for (int i = 0; i < n; i++) {
            String x = br.readLine();

            if (x.equals("0")) {
                if (queue.isEmpty()) {
                    bw.write("0\n");
                }
                else {
                    bw.write(queue.poll() + "\n");
                }
            }
            else {
                queue.offer(Integer.parseInt(x));
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }

}