[JAVA]BOJ(백준) - 절댓값 힙 - 11286

문제 내용

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

11286번: 절댓값 힙

 

---

문제 접근 방법

x가 0일때 절댓값이 가장 작은수를 출력하라는 말을듣고 우선순위큐를 사용할 생각을 할 수 있었다. 하지만 기존의 우선순위와는 다르게 큐를 만들면서 정렬을 할때 

 

절댓값 기준으로 한번 정렬.

절댓값이 같다면 오름차순으로 정렬.

 

이렇게 두번 정렬이 필요하다. 그러기 위해선 우선순위큐를 만들때 Comparator로 객체를 생성해 값 o1, o2를 비교해주기로 했다.

참고로 Comparator는 return값이 정수이고 기본적으로 두가지를 알고 있어야 한다.

 

선행 원소 o1이 후행 원소 o2보다 크다면 return 값이 양수로 나오고 o1과 o2값을 바꿔준다.

선행 원소 o1이 후행 원소 o2보다 작다면 return 값이 음수로 나오고 o1과 o2값을 그대로 둔다.

 

만약 분기문을 사용하지 않고 return 값을 정하고 싶을땐 return o1-o2; 를 사용하면 된다.

하지만 이문제에선 x의 값의 범위는 정수형 최소~최대 범위 이기 때문에 o1-o2 연산시 underflow 혹은 overflow가 발생할 수 있기때문에 분기문을 활용한 대소비교를 해줘야 한다.

 

Comparator 에 대한 자세한 내용은 아래 블로그를 참고하길 바란다.

정말 자세하고 알아듣기 쉽게 잘 설명해 놓으셨다!!

https://st-lab.tistory.com/243

자바 [JAVA] - Comparable 과 Comparator의 이해

 

---

 

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

public class BOJ_11286 {
	static int N;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				Integer a = Math.abs(o1);
				Integer b = Math.abs(o2);
				
				if(a > b) {//절댓값 비교
					return 1;
				}else if(a < b) {
					return -1;
				}else {// 절댓값이 같다면
					if(o1 > o2) { // 원래 원소를 비교
						return 1;
					}else if(o1 < o2) {
						return -1;
					}else {
						return 0;
					}
				}
			}
		});
		
		N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			int x = Integer.parseInt(br.readLine());
			if(x==0) {
				if(pq.isEmpty()) {
					sb.append(0).append("\n");
				}else {
					sb.append(pq.poll()).append("\n");
				}
			}else {
				pq.add(x);
			}
		}
		System.out.println(sb);
	}	
}

 

---

마치며

이번에는 queue를 쓰는 정렬보다는 Comparator 공부를 할 수 있는 기회였다. 다른 문제를 풀때 특별한 기준으로 정렬해야 할때 Comparator를 고려해보도록 하자.