알고리즘 풀이(JAVA) - 백준 알고리즘(절댓값 힙)

By on September 23, 2019

문제

문제 링크 : (절대값 힙) https://www.acmicpc.net/problem/11286

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
배열에 정수 x (x ≠ 0)를 넣는다.
배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.
만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다.
입력되는 정수는 -2³¹보다 크고, 2³¹보다 작다.

풀이

양수 음수를 처리하기 위해 저장 큐를 분리 함.
양수는 순차 정렬을, 음수는 역순으로 정렬을 하여 처리 함.

소스

절댓값 힙

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

public class Baekjoon_11286 {
	public static void main(String[] args){
		
        try(BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));){
        	int N = Integer.parseInt(reader.readLine());

        	Queue<Integer> positive = new PriorityQueue<>(Comparator.naturalOrder());
        	Queue<Integer> negative = new PriorityQueue<>(Comparator.reverseOrder());
        	
        	for(int i = 0; i < N; i++) {
        		int input = Integer.parseInt(reader.readLine());
        		if(input != 0) {
        			if(input > 0) {
        				positive.add(input);
        			}else {
        				negative.add(input);
        			}
        		}else {
	        		if(positive.isEmpty() && negative.isEmpty()){
	        			System.out.println(0);
	        		}else {
	        			if(positive.isEmpty()) {
	        				System.out.println(negative.poll());
	        			}else if(negative.isEmpty()) {
	        				System.out.println(positive.poll());
	        			}else {
	        				if(Math.abs(negative.peek()) == Math.abs(positive.peek())){
	        					System.out.println(negative.poll());
	        				}else {
	        					if(Math.abs(negative.peek()) > Math.abs(positive.peek())){
	        						System.out.println(positive.poll());
	        					}else {
	        						System.out.println(negative.poll());
	        					}
	        				}
	        			}
	        		}
        		}
        	}
        }catch(Exception e){
            e.printStackTrace();
        }
    }
}