[Java] baekjoon_11286 : 절댓값 힙

자료 구조, 우선순위 큐

절댓값 힙 : Silver1

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

PriorityQueue

보통 PriorityQueue는 오름차순으로 정렬되는데, 만약 두 요소의 절댓값이 같다면, 우리는 원래 값의 차이에 따라 우선순위를 결정하고 싶습니다.

예를 들어, 절댓값이 같은 두 정수가 1과 -1이라고 가정해보자. 이 경우, a - b를 계산하면 1 - (-1) = 2이 된다.

이는 두 요소의 차이를 나타내며, 이 값이 크면 클수록 원래 값이 더 크다. 

즉, 두 요소가 동일한 절댓값을 가질 때, 더 큰 값을 우선으로 정렬하여 최소값이 먼저 나오도록 하고자 하는 것이다.

 

 

첫 번째 작성한 코드

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

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static void main(String[] args) throws Exception {
    int N = Integer.parseInt(br.readLine());

    PriorityQueue<Integer> pq = new PriorityQueue<>(new AbsComparator());

    for (int i = 0; i < N; i++) {
      int x = Integer.parseInt(br.readLine());
      if (x == 0) {
        if (pq.isEmpty()) {
          bw.write("0\n");
        } else {
          bw.write(pq.poll() + "\n");
        }
      } else {
        pq.offer(x);
      }
    }

    bw.flush();
    br.close();
    bw.close();
  }
  
  // Comparator 구현
  static class AbsComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer a, Integer b) {
      int absA = Math.abs(a);
      int absB = Math.abs(b);
      if (absA == absB) {
        return a - b;
      } else {
        return absA - absB;
      }
    }
  }
}

 

ㄴ 처음에는 람다식을 이용하지 않고 Comparator 객체를 직접 생성하여 PriorityQueue를 초기화하는 방법을 사용했다.

ㄴ AbsComparator 클래스가 Comparator<Integer> 인터페이스를 구현하고, 이 Comparator를 사용하여 PriorityQueue를 초기화했다.

ㄴ compare 메서드에서는 두 정수의 절댓값을 비교하여 절댓값이 같으면 원래 값의 차이를 반환하고, 절댓값이 다르면 절댓값의 차이를 반환하여, 이 Comparator에 따라 요소가 정렬되어 들어가게 된다.

 

 

두 번째 작성한 코드

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

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static void main(String[] args) throws Exception {
    int N = Integer.parseInt(br.readLine());

    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> 
      Math.abs(a) == Math.abs(b) ? a - b : Math.abs(a) - Math.abs(b)
    );

    for (int i = 0; i < N; i++) {
      int x = Integer.parseInt(br.readLine());
      if (x == 0) {
        if (pq.isEmpty()) {
          bw.write("0\n");
        } else {
          bw.write(pq.poll() + "\n");
        }
      } else {
        pq.offer(x);
      }
    }
    
    bw.flush();
    br.close();
    bw.close();
  }
}

 

ㄴ 람다식을 이용해보았다.

 

(a, b) -> Math.abs(a) == Math.abs(b) ? a - b : Math.abs(a) - Math.abs(b)

 

ㄴ 이 람다식은 Comparator의 compare 메서드를 구현한 것이다. 

ㄴ compare 메서드는 두 개의 요소를 비교하여 정렬 순서를 결정한다.

ㄴ 람다식에서는 a와 b를 비교하여 두 요소의 절댓값이 같으면 원래 값의 차이를 반환하고, 절댓값이 다르면 절댓값의 차이를 반환한다.

즉, PriorityQueue는 요소를 추가할 때마다 해당 Comparator에 따라 정렬되며, 여기서는 요소의 절댓값을 기준으로 정렬되어 최소 힙처럼 동작하게 된다.

따라서 이 PriorityQueue를 사용하면 절댓값이 작은 순서대로 요소가 정렬되어 들어가게 되고, 최소값을 빠르게 찾을 수 있다.