절댓값 힙 (백준 11286)

문제분석

⭐지문파악 중요
1. 절댓값 힙(자료구조) 구현하기
1) 배열에 정수x(x!=0)를 넣는다
2) 배열에서 절댓값이 가장 작은 값을 출력한 후 그 값을 배열에서 제거, 절댓값이 가장 작은 값이 여러개면 그중 가장 작은 수를 출력하고 그 값을 배열에서 제거.
ex. 1과 -1은 절댓값이 같음 -> 더 작은 -1
2. x가 0이 아니라면 배열에 x라는 값을 추가, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거.
3. 입력에서 0이 주어진 횟수 만큼 답을 출력, 배열에 비어있는데 절댓값이 가장 작은 값을 출력할때는 0을 출력.

• 데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요 -> 우선순위 큐
  • 음수우선 정렬

슈도코드

우선순위 큐 선언
  - 절대값 기준으로 정렬되도록 설정
  - 절댓값이 같으면 음수 우선 정렬
for(N만큼 반복){
	if(x==0) 큐가 비어 있을때 0을 출력, 비어 있지 않을때는 큐의 front값 출력.
	else(x!=0) 큐에 add
}

정답

package A0study;

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

public class p11286_절댓값힙 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // 우선순위 큐 custom
        PriorityQueue<Integer> myQueue = new PriorityQueue<>((o1, o2) -> {
            int abs1 = Math.abs(o1);
            int abs2 = Math.abs(o2);
            if(abs1 == abs2) {
                return o1 - o2;     // 절댓값 같으면 음수 우선  (Comparator는 결과가 음수면 o1을 앞에 둔다)
            }
            return abs1 - abs2;     // 절댓값 작은 수 우선
        });

        for(int i=0; i<N; i++) {
            int request = Integer.parseInt(br.readLine());
            if(request == 0) {
                if(myQueue.isEmpty()) {
                    System.out.println("0");
                } else {
                    System.out.println(myQueue.poll());
                }
            } else {
                myQueue.add(request);
            }
        }
    }
}

요약

큐에 값을 넣거나 꺼낼 때마다 PriorityQueue가 Comparator 로직을 돌려서 앞에 올 값(우선순위 높은 값)을 정한다.