[백준 11286] 절댓값 힙

[문제 바로가기]👇

11286번: 절댓값 힙

 

💡풀이💡

출력할 때 우선순위를 보면

절댓값이 가장 작은 값을 출력
절댓값이 가장 작은 값이 여러 개 일때, 가장 작은 수를 출력

이렇게 되어 있기 때문에 최소 힙인 우선순위 큐를 사용!

 

절댓값이 가장 작은 값이 여러 개 있을 때는 가장 작은 수가 나올 수 있도록 정렬해야 함

>>자바에서 기본적으로 제공하지 않는 정렬이기 때문에 Comparator를 사용해서 직접 정렬 구현

 

1. 절댓값 힙 구현

x가 0일 때 : 배열에서 출력

• 이때, 배열이 비어 있다면 0을 출력!

x가 0이 아닐 때 : x를 배열에 추가

for(int i=0; i<N; i++) {
	int x = Integer.parseInt(br.readLine());
	if(x == 0) {
		if(!q.isEmpty()) {
			sb.append(q.poll()).append("\n");
		}
		else sb.append(0).append("\n");
	}
	else {
		q.offer(x);
	}
}

 

 

2. 우선 순위 큐 사용자 정의 정렬 구현

Comparator 의 Compare 메서드를 오버라이드해서 구현

• 절댓값으로 먼저 정렬
• 절댓값이 같다면(r==0) 수의 크기로 정렬

PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> 
	{
            int r = Integer.compare(Math.abs(o1), Math.abs(o2));
            if(r == 0) r = Integer.compare(o1, o2);
            return r;
	}
);

 

 

3. 전체 코드

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

public class B11286 {

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

}