[BaekJoon 11286번 / JAVA] 절댓값 힙

Question

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

11286번: 절댓값 힙

 

---

💡 Solution

일반 큐와 달리 우선순위 큐는 기본적으로 오름차순 정렬입니다. 따라서 오름차순 정렬이 필요할 때는 아래와 같이 기본적으로 선언하면 됩니다.

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

 

우선순위 큐를 내림차순 정렬하려면 아래와 같이 선언하면 됩니다.

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

 

이번 문제에서는 절댓값을 기준으로 정렬을 해야 하므로, Comparator의 compare 메서드를 오버라이딩하여 절댓값을 기준으로 정렬할 수 있게끔 해주어야 합니다. 

배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

 

즉, 절댓값이 작은 값이 앞으로 오게끔 해주면 됩니다. 절댓값이 같다면 원래의 수를 비교해서 더 작은 값을 앞으로 오게 해주면 되는데, 우선순위 큐는 앞서 말했듯이 기본적으로 오름차순 정렬이므로, 우리는 절댓값을 기준으로 정렬하는 것에만 신경쓰면 됩니다. 참고로, compare 함수를 구현할 때 return 값을 양수를 주면 순서를 바꾼다는 의미이고, 음수를 주면 바꾸지 않겠다는 의미입니다. 

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
        if (Math.abs(o1) > Math.abs(o2)) {
            return Math.abs(o1) - Math.abs(o2);
        } else if(Math.abs(o1) == Math.abs(o2)) {
            return o1 - o2;
        } else {
            return -1;
        }
    }
});

 

위 코드를 한 나눠서 본다면

if (Math.abs(o1) > Math.abs(o2)) {
    return Math.abs(o1) - Math.abs(o2);
}

기본적으로 우선순위 큐는 오름차순으로 정렬되어 있는 상태에서, 절댓값을 기준으로 앞쪽 값이 더 크다면 순서를 바꿔줍니다.

else if(Math.abs(o1) == Math.abs(o2)) {
    return o1 - o2;
}

만일 절댓값을 기준으로 두 값이 같다면 순서를 바꾸지 않아도 됩니다.

 

💻 Code

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

public class BJ11286 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if (Math.abs(o1) > Math.abs(o2)) {
					return Math.abs(o1) - Math.abs(o2);
				} else if(Math.abs(o1) == Math.abs(o2)) {
					return o1 - o2;
				} else {
					return -1;
				}
			}
		});
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			if (x == 0) {
				if (pq.isEmpty()) {
					sb.append(0).append("\n");
				} else {
					sb.append(pq.poll()).append("\n");
				}
			} else {
				pq.offer(x);
			}
		}
		System.out.println(sb);
	}

}