(Java/자바) - 백준(BOJ) 11286번 :절댓값 힙

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

11286번: 절댓값 힙

---

• 문제 : 

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

 

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

 

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

 

 

---

• 풀이 :

힙(우선순위 큐)를 사용한 문제였습니다.

 

자바 Collections의 PriorityQueue을 사용했고 이 때 Comparator를 람다 형태로 절댓값 비교 함수로 오버라이드 하였습니다. 또한, 절댓값이 같은 두 수인 경우 ( a = -1, b = 1 ) 더 작은 수를 찾기 위해 a-b를 리턴하여 오름차순 정렬하였습니다.

 

풀이는 다음과 같습니다.

 

 

1.  N만큼 입력을 받는다. N이 0일 경우 pq에서 poll을 하여 가장 절댓값이 작은 값을 출력한다.

 

2. 0이 아닐 경우 pq에 넣는다.

 

 

 

---

• 소스코드 : 

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

public class Main{
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a,b) ->{
			int tmp = Math.abs(a)- Math.abs(b);
			return tmp == 0? a-b : tmp;
		} );
		int N = Integer.parseInt(br.readLine());
		int input;
		while(N-->0) {
			input = Integer.parseInt(br.readLine());
			if (input==0) sb.append((pq.isEmpty()?0:pq.poll())).append("\n");
			else pq.add(input);
		}
		System.out.println(sb.toString());
	}
}