[Java] 백준(실버-1) 11286번 - 절댓값 힙

문제 풀이

---

이번 문제는 우선순위 큐를 이용해 요구한 힙을 구현하면 되는 문제이다.

아이디어 도출

이번 문제는 최대 힙 문제와 같이 PriorityQueue를 사용해 Comparator의 compare() 메서드를 오버라이딩하여 큐에 삽입되는 데이터를 주어진 조건대로 정렬해야 한다.

문제를 잘 살펴보면, 큐의 우선순위를 절댓값이 작은 순서에서 숫자가 작은 순서로 제거해야 한다는 것을 알 수 있다.

1. 두 수(o1, o2)의 절댓값이 같다면, 두 수 중 더 큰 수를 기준으로 우선순위가 높게 책정되도록 한다.
2. 두 수의 절댓값이 다르다면, 두 수의 절댓값의 차 즉, 절댓값이 작은 수의 우선순위가 높게 책정되도록 한다.
3. 결과적으로 절댓값이 작은 순서로 정렬되도록 한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

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));
        
        // 람다식으로 풀이
        // 절댓값이 작은 순서로 정렬된다.
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> {

            // 두 수의 절댓값이 같고 앞 수가 더 크다면, 더 큰수의 우선순위를 높게 설정된다.
            if(Math.abs(o1) == Math.abs(o2)) {
                return o1 > o2 ? 1 : -1;
            }

            // 두 수의 절댓값이 다르다면 절댓값이 작은 수의 우선순위가 높게 설정된다.
            return Math.abs(o1) - Math.abs(o2);

        });

        int N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(br.readLine());
            
            // 만약 입력값이 0보다 큰 자연수라면 우선순위 큐에 삽입.
            if(num != 0) {
                q.offer(num);
                continue;
            }
            
            // 0일 때 우선순위 큐가 비어있다면 0을, 비어있지 않다면 가장 작은 수를 꺼낸다.
            if(!q.isEmpty()) {
                bw.write(q.poll()+"\n");
            } else {
                bw.write("0"+"\n");
            }
            
        }

        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.