[백준_11286/JAVA] 절댓값 힙

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

문제풀이

데이터를 삽입할 때 마다 절댓값과 관련된 정렬이 필요하므로, 우선순위 큐로 문제를 해결할 수 있다.
단, 이 문제는 절댓값 정렬이 필요해 우선순위 큐의 정렬 기준을 직접 정의 해야 한다.

1. x=0 인 경우
   • 큐가 비어 있을 때는 0을 출력
   • 비어 있지 않을 때는 절댓값이 최소인 값을 출력.
     • 단, 절댓값이 같다면 음수를 우선하여 출력
2. x=0이 아닌 경우
   • add로 큐에 새로운 값을 추가하고, 우선순위 큐 정렬 기준으로 정렬한다.

이 문제는 두 개 값을 비교해 어떤 값이 앞에 오고, 뒤에 오는지를 정하는 기준을 정의하는 Comparator로 풀이해야한다.

절댓값이 작은 순으로 front에 가깝도록 우선순위 기준을 정의해야 한다.
Comparator는 반환값 만으로 두 값을 비교한다.

 

핵심
1. 우선순위 큐를 사용한다. 그 '우선순위'를 문제 조건에 맞게 재정의하자.
2. 그 재정의는 Comparator로 구현

코드

package dataStructure;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

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());
        StringBuffer bf=new StringBuffer();

        // 삽입 후 절댓값이 작은 값을 기준으로 front에 위치시킨다.
        // 우선순위 큐 정렬 기준을 만들어야한다.
        PriorityQueue<Integer> myQueue=new PriorityQueue<>((o1,o2)->{
            int FirstABS=Math.abs(o1);
            int SecondABS=Math.abs(o2);

            if(FirstABS==SecondABS) {
                return o1>o2?1:-1;
            }else {
                return FirstABS-SecondABS;
            }
        });

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

            if(num==0) {
                if(myQueue.isEmpty()) {
                    System.out.println("0");
                }else {
                    System.out.println(myQueue.poll());
                }
            }else {
                myQueue.add(num);
            }
        }
    }
}