백준 11286 절댓값 힙 [JAVA]

문제 해석

• 연산 개수 N을 입력받고 정수(x)를 입력받는다.
  • x가 0이면 절댓값이 가장 작은 값을 출력한다.
  • x가 0이 아니면 배열에 x라는 값을 넣는다.
  • x가 0인데 배열이 비어있으면 0을 출력한다.
• 전/전전 POST였던 최대/최소 힙문제와 거의 유사한 문제이다. 다만 절댓값이 작은 수를 출력해야한다.
• 기존 로직을 그대로 가되 절댓값으로 비교하는 코드만 추가하면 되는 문제이다.

//절댓값의 크기를 비교하는 클래스 (오름차순 정렬)
    public static class compareAbsNum implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2){
            if(Math.abs(o1) > Math.abs(o2)){ //절댓값이 클 경우 
                return 1; // 1반환
            }else if(Math.abs(o1) < Math.abs(o2)){ //절댓값이 작을 경우
                return -1; //-1반환
            }else{ //절대값이 같을 경우
                if(o1 >= o2){ //o1이 o2보다 같거나 클 경우 
                    return 1; // 1반환
                }else{ //o1이 o2보다 작을 경우
                    return -1; // -1반환
                }
            }
        }
    }
 
 //위의 클래스를 작성하고 아래와 같이 사용하면 절댓값으로 비교하는 코드가 완성된다.
 PriorityQueue<Integer> Queue = new PriorityQueue <>(new compareAbsNum());
 

• 위의 로직을 제외하면 기존 방식과 동일하기 때문에 전에 작성한 POST인 최대_힙, 최소_힙을 참고하면 된다.

코드

import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

    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()); //연산 개수
        //절댓값이 최소인 값을 먼저 추출한다. (default가 최소인 값부터 출력하기 때문에) 
        PriorityQueue<Integer> Queue = new PriorityQueue <>(new compareAbsNum());

        while(N --> 0){
            int x = Integer.parseInt(br.readLine()); //연산
            if(x == 0){ //0이면 가장 작은 값을 출력하고 배열에서 제거
                if(Queue.isEmpty()){ //배열이 비어있으면 0을 출력
                    sb.append(0).append("\n");
                }else{ //배열이 안비어있으면
                    sb.append(Queue.poll()).append("\n");
                }
            }else{ //0이 아니고, 자연수라면 배열에 x를 추가
                Queue.add(x);
            }
        }
        br.close();
        System.out.println(sb);
    }

    //절댓값의 크기를 비교하는 클래스 
    public static class compareAbsNum implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2){
            if(Math.abs(o1) > Math.abs(o2)){ //절댓값이 클 경우 
                return 1;
            }else if(Math.abs(o1) < Math.abs(o2)){ //절댓값이 작을 경우
                return -1;
            }else{ //절대값이 같을 경우 
                if(o1 >= o2){
                    return 1;
                }else{
                    return -1;
                }
            }
        }
    }
}

결과

느낀 점

최대힙, 최소힙문제와 유사하고 기존에 comaprator 비교하는 건 전에 문제로 접해본적이 있는 것 같아서 크게 어려움 없이 풀 수 있었다.