절댓값 힙(백준_11286번)

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

11286번: 절댓값 힙

문제 설명

이 문제는 숫자가 입력 되면 2가지 조건으로 정렬을 하면 된다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다

 

문제에 대한 아이디어

이 문제는 우선순위 큐를 사용해 해결 하라는 문제이다. 자바에서 우선순위 큐를 처음 사용해보는데 신기한 부분이 있었다.

바로 자바는 비교하는 부분을 람다식으로 쉽게 설정 할 수 있다는 것이다. 이것이 자바만의 람다식만의 장점인 것 같다.

양수	첫번째 매개변수가 더 큰 값으로 판단
0	같은 값으로 판단
음수	첫번째 매개변수가 더 작은 값으로 판단

비교 람다식에서 알아야 할 부분은 위의 표이다. 리턴 값이 각각 양수, 0, 음수에 따라 우선순위가 달라진다.

• 자바의 우선순위 큐 디폴트(최소힙)

PriorityQueue<Integer> pq = new PriorityQueue<>();

• 자바의 우선순위 큐(최대힙)

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

 

구현

• 우선순위 큐 선언

PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
    int first_abs = Math.abs(o1);
    int second_abs = Math.abs(o2);
    if(first_abs == second_abs)
        return o1 > o2 ? 1 : -1; //절대값이 같을 경우 음수부터 정렬
    else
        return first_abs - second_abs; //절대값 기준으로 정렬
} );

• 문제 해결 부분

for (int i = 0; i < n; i++) {
    num = sc.nextInt();
    if(num == 0){
        if(pq.isEmpty()){
            System.out.println(0);
        }
        else {
            int a = pq.poll();
            System.out.println(a);
        }
    }
    else {
        pq.add(num);
    }
}

 

전체 코드

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_11286.java

GitHub - Heron-Woong/CodingTest_Practice