Java 백준 문제풀이 (46) 11286 : 절댓값 힙

 

 

문제 이름이 절댓값 힙인 것을 보면 유추할 수 있겠지만, Priority Queue(우선순위 큐)를 사용해서 풀어야하는 문제다.

힙과 우선순위큐의 상관관계가 궁금하다면 다음 링크를 참고.

 

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

음.. 제목에서 이미 푸는 방법을 다 알려주고 있어서 IDE를 써서 풀면 굉장히 쉬운 문제, IDE를 쓰지 못하면 사람에 따라 힘든 문제일 수 있겠다.

 

이 문제를 풀기 위해 필요한 지식은 오직 힙과 우선순위 큐의 상관관계, 그리고 우선순위 큐를 재설정하는 방법 뿐이다.

Comparator를 재정의해본 사람들에게는 아주 익숙하겠지만, 해본 적 없더라도 금방 배울 수 있으니 걱정할 것 없다.

 

 

        PriorityQueue<Integer> queue = new PriorityQueue<>(
                new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o1 - o2;
                    }
                }
        );

 

 

그냥 PriorityQueue 내부에서 익명 클래스 만들어서 재설정해주면 된다.

참고로 현재 보이는 값은 그냥 기본 설정이며 o1에서 o2를 뺐을 때 결과값이 양수면 오름차순, 음수면 내림차순이다.

이건 이해할 필요가 없다. 그냥 규칙임.

궁금하면 소스를 뜯어보자.

 

우리가 만들어줘야하는 조건은

1. 절대값끼리 비교해서 더 작은 수를 앞으로

2. 만약 절대 값이 같을 경우 기존 값이 작은 수를 앞으로

 

 

 

        PriorityQueue<Integer> queue = new PriorityQueue<>(
                new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        if (Math.abs(o1) == Math.abs(o2)) {
                            return o1 - o2;
                        } else {
                            return Math.abs(o1) - Math.abs(o2);
                        }
                    }
                }
        );

 

 

그런데 지저분해서 마음에 안 든다.

람다식으로 표현하면 훨씬 짧아지지 않을까?

그건 직접 해보삼

사실 문제 자체도 우선순위 큐만 재정의하면 끝인 문제라 나머지는 알아서 다 풀 수 있을 것이다.

정답은 아래에

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

import java.util.*; import java.io.*;   public class Main {     public static void main(String[] args) throws Exception {         // 첫 번째 줄 연산 개수 N         // N개의 줄에 관련된 정보 나타내는 정수         // 0이 주어진 횟수만큼 절대값 중 가장 작은 수, 둘 다 있으면 둘 중 작은 수 출력하고 제거           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int N = Integer.parseInt(br.readLine());           PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> {             if (Math.abs(o1) == Math.abs(o2)) {                 return o1 - o2;             } else {                 return Math.abs(o1) - Math.abs(o2);             }         }         );           StringBuilder sb = new StringBuilder();           for (int i=0; i<N; i++) {             int n = Integer.parseInt(br.readLine());               if (n==0) {                 if (queue.peek() == null) {                     sb.append(0).append("\n");                 } else {                     sb.append(queue.poll()).append("\n");                 }             } else {                 queue.add(n);             }         }           System.out.println(sb);     } } Colored by Color Scripter

cs