11286번 - 절댓값 힙

1️⃣ PriorityQueue

 

✏️ 풀이 과정

절댓값이 작은 순서대로 출력하는 힙을 만드는 문제입니다. 기본 PriorityQueue의 약간의 조작을 가해주면 구현할 수 있습니다.

 

기본적인 아이디어는 음수를 입력받으면 -1를 곱해서 삽입하는 것입니다. 이렇게 하면 절댓값 순으로 정렬되는 것을 예상할 수 있습니다. 하지만 꺼낼 때 어떻게 다시 음수로 복원할 수 있을까요? 이를 해결하기 위해 새로 클래스를 선언해야 합니다. 클래스를 선언해서 음수 여부를 표시함과 동시에 Comparable을 implements하고 compareTo 메서드를 정의함으로써 절댓값 힙을 바로 구현할 수 있습니다.

 

compareTo에서 값이 같을 때는 음수인 경우를 우선시하도록 프로그래밍해야합니다.(절댓값이 같을 경우 작은 것 우선) 마지막으로 출력할 때 isNegative를 확인하여 음수일 경우 -1를 곱해주면 해결됩니다.

 

💻 코드

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

public class Main {
	
	static class Abs implements Comparable<Abs>{
		int val;
		boolean isNegative;
		public Abs(int val, boolean isNegative) {
			this.val = val;
			this.isNegative = isNegative;
		}
		@Override
		public int compareTo(Abs o) {
			if(this.val == o.val) {
				if(this.isNegative) {
					return -1;
				}
				return 1;
			}
			return this.val-o.val;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int x;
		PriorityQueue<Abs> q = new PriorityQueue<>();
		StringBuilder sb = new StringBuilder();
		Abs tmp;
		for(int i=0;i<N;i++) {
			x = Integer.parseInt(br.readLine());
			if(x == 0) {
				if(q.isEmpty()) {
					sb.append(0+"\n");
				} else {
					tmp = q.poll();
					if(tmp.isNegative) {
						sb.append(-1 * tmp.val+"\n");
					} else {
						sb.append(tmp.val+"\n");
					}
				}
			} else {
				if(x >= 0) {
					q.offer(new Abs(x, false));
				} else {
					q.offer(new Abs(-1 * x, true));
				}
			}
		}
		System.out.print(sb);
		br.close();
	}
}