[Baekjoon] 11286 - 절댓값 힙

📝 문제

 

 

🔑 풀이 과정

· 문제에 나온 절댓값 힙을 Comparator 인터페이스를 구현하는 방법으로 생성했다.

 

· PriorityQueue 클래스는 생성할 때 인자에 Comparator을 넣을 수 있다. Comparator 인터페이스를 사용하는 방법을 여기를 참고하자!

 

· 절댓값이 가장 작은 값을 제거하고 출력해야 하므로, 절댓값이 작은 값이 더 높은 순위를 갖게 한다.

그리고 만약 절댓값이 가장 작은 것이 여러개라면 그 중에서 가장 작은값을 출력해야 하므로(즉, 음수값을 출력하라는 거다) 절댓값이 같을때는 음수가 더 높은 순위를 갖게 한다.

 

· 나 같은 경우는 람다식이 익숙치 않아서 따로 class 를 생성하는 방식으로 풀이했다.

 

 

🔓 답안

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine()); //연산의 개수

        PriorityQueue<Integer> queue = new PriorityQueue<>(new AbsComparator()); //힙 생성

        for(int i = 0; i < N; i++){
            int x = Integer.parseInt(br.readLine());

            if(x != 0){
                queue.add(x);
            }
            else if(x == 0){
                if(queue.isEmpty()){ //만약 배열이 비어있으면 0 출력
                    sb.append(0).append("\n");
                }
                else{ //가장 절댓값 작은 값 출력
                    int item = queue.remove();
                    sb.append(item).append("\n");
                }
            }
        }

        //출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }

}

class AbsComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        if(Math.abs(o1) != Math.abs(o2)){
            return Math.abs(o1) - Math.abs(o2);
        }
        else{ //절댓값이 같은 경우 더 작은값을 최소로
            return o1 - o2;
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 자료 구조

- 우선순위 큐