[알고리즘] 백준 11286 - 절댓값 힙

분류 : 자료구조

1. 문제

https://www.acmicpc.net/problem/11286
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

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

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

2. 입력

첫째 줄 : 연산의 개수 N
다음 N개의 줄 : 연산에 대한 정보를 나타내는 정수 X
X가 0이 아님 -> 배열에 X라는 값 추가
X가 0 -> 배열에 절대값이 가장 작은 값 출력, 배열에서 값 제거

3. 풀이

최소힙과 동일한 방식인데 절대값만 계산해주면 된다.
자바에서는 PriorityQueue를 이용해 구현할 수 있다.

• 기본은 우선순위가 낮은 숫자 부여

1. PriorityQueue의 Compare 메소드를 절대값을 비교하도록 오버라이드 한다
   1) o1과 o2의 절대값이 같을 떄 -> o1이 양수면 1, 음수면 -1
   2) o1의 절대값이 크면 양수
   3) o1의 절대값이 작으면 음수 리턴
2. 입력값을 순서대로 받으면서 큐에 넣거나 반환한다.

4. 코드

import java.util.PriorityQueue;
import java.util.Scanner;

//20211228
public class minAbsoluteHeap {
    public static void solution(){
        Scanner in = new Scanner(System.in);

        //연산 개수
        int N = in.nextInt();

        //Comparator의 compare 메소드 오버라이드
        //절대값으로 최소힙 정렬
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
            int abs1 = Math.abs(o1);
            int abs2 = Math.abs(o2);

            //절대값이 같은 경우
            if(abs1==abs2){
                //os가 양수면(더 크면) 1 return
                return o1 > o2 ? 1 : -1;
            }

            //o1이 더 크면 양수 리턴, 작으면 음수 리턴
            return abs1-abs2;
        });

        for(int i=0; i<N;i++){
            int num = in.nextInt();

            //0이 아닐 떄 배열(최소힙)에 값 추가
            if(num!=0){
                queue.offer(num);
            }
            //절대값 가장 작은 값 출력, 배열에서 제거
            else{
                if(queue.isEmpty()){
                    System.out.println('0');
                }
                else{
                    System.out.println(queue.poll());
                }
            }
        }
    }

}