[백준] 11286번. 절댓값 힙 (JAVA)

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

---

문제

---

풀이

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());
        PriorityQueue<Integer> sortedNumbers = new PriorityQueue<>((o1, o2) -> {
            int x = Math.abs(o1);
            int y = Math.abs(o2);
            if(x == y){
                return o1 > o2 ? 1 : -1;
            }
            return x - y;
        });

        for(int i = 0; i < n; i++){
            int x = Integer.parseInt(br.readLine());
            if(x == 0){
                if(sortedNumbers.isEmpty()){
                    System.out.println(0);
                }else{
                    System.out.println(sortedNumbers.poll());
                }
            }else{
                sortedNumbers.offer(x);
            }
        }

    }
}

 

우선순위 큐를 람다식을 통해 원하는 방식으로 정렬하는 문제이다. 

PriorityQueue<Integer> sortedNumbers = new PriorityQueue<>((o1, o2) -> {
    int x = Math.abs(o1);
    int y = Math.abs(o2);
    if(x == y){
        return o1 > o2 ? 1 : -1;
    }
    return x - y;
});

 

이 부분을 보면 o1, o2를 정렬할 규칙을 정해준다. 일단 절댓값의 순서대로 정렬할 것이기 때문에 절댓값을 한 숫자 두 개를 선언해 주고, 절댓값이 같은 경우 음수가 앞에 오게 할 것이다.

순서대로 따져보면 이렇게 된다.

1. o1과  o2가 들어온다. 우선순위 큐에서 o1이 앞에 오는 숫자라고 생각하면 된다.(즉, poll()을 했을 때 먼저 나오는 숫자가 된다는 것이다.)

2. x와 y에 각각 o1과 o2의 절댓값을 저장한다.

3. 절댓값이 같다면 o1과 o2의 크기를 비교한다.(절댓값이 같기때문에 부호를 비교한다고 생각해도 된다.)

4. o1 > o2 (o1의 부호가 양수이고, o2의 부호가 음수)라면 1을 반환한다. (우선순위 큐는 양수가 반환됐을 경우에 순서를 바꾼다.) -> 이 과정을 통해 음수가 앞에, 양수가 뒤에 위치하게 할 수 있다.

5. 절댓값이 같지 않다면 절댓값의 차를 통해 정렬한다. (절댓값이 x가 크면 양수가 반환되므로 순서를 변경한다.)

 

여기서 실수하기 쉬운 부분은 if를 통해 절댓값이 같은 경우를 비교한 다음에 else 문을 통해 절댓값이 다른 경우를 생각하는 것이 아닌 함수와 동일하게 return을 통해 빠져나오는 것을 생각해야 한다는 것이다.