[백준/자료구조-큐] 11286: 절댓값 힙 - 자바

문제

---

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

11286번: 절댓값 힙

 

풀이

---

다른 사람은 어떻게 느꼈을지 모르겠지만 본인에게는 어려웠던 문제 

특히 "배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다." 라는 조건을 어떻게 해야할지 감이 잡히지 않았음.

 

우선순위 큐를 생성하면서 비교 조건을 

• 절대값이 같을 때 음수 -> 양수 로 정렬을 해주고 
• 절대값이 같지 않은 수일 때 오름차순 정렬을 하였음. ( -1, 1, 2,-2 일 때 -1,1,-2,2 로 정렬)

다시말해, 

문제에서 포인트는 우선순위 큐의 비교조건을 comparator를 사용하여 compare를 재정의 하였음

(1, 1, -1, -1, 2, -2 가 들어온다면 -1, -1, 1, 1, -2, 2 로 정렬시킴)

 

package _UnsolvedProblem;

import java.io.*;
import java.util.*;

public class BOJ_11286 {
	public static void main(String[] args) throws Exception {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
			
				@Override
				public int compare(Integer o1, Integer o2) {
					if (Math.abs(o1) == Math.abs(o2)) return o1 - o2;
					return Math.abs(o1) - Math.abs(o2);
				}
		});
		
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i <n; i++) {
			int num = Integer.parseInt(br.readLine());
			if(num!=0) queue.offer(num);
			else {
				if(queue.size() == 0) bw.write("0\n");
				else bw.write(queue.poll()+"\n");
			}
		}
		bw.flush();
		bw.close();
	}
}