[Java] 백준 BOJ / 11286번: 절댓값 힙

절댓값 힙

문제

---

문제 설명

우선순위 큐를 사용하여 자료구조를 구현하는 문제이다.

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.

우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.

말 그대로 우선순위를 정하는 큐인데 우선순위를 정하는 방법엔 두가지가 있다.

• java.lang.Comparable : 원소 스스로 다른 원소와 자신을 비교할 때 사용하는 방법
  • compareTo 메서드를 구현해야 함
  • 자기 자신과 매개변수 객체를 비교

    public class ClassName implements Comparable<Type> {
       
       @Override
       public int compareTo(Type o) {
           // 비교 구현
       }
    }

• java.util.Comparator : 두 개의 원소 대소 비교를 비교자가 판단하는 방법

  • compare 메서드를 구현해야 함

  • 두 매개변수 객체를 비교

    // 클래스에서 사용할 때
    public static class ClassName implements Comparator<Type> {
       @Override
       public int compare(Type o1, Type o2) {
           return o1 - o2;
       }
    }
    
    // Priority Queue에서 사용할 때
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
       @Override
       public int compare(Integer o1, Integer o2) {
           return o1 - o2;
       }
    });

위와 같은 방법으로 우선순위 큐를 문제 조건에 맞게 구현하면 되는 문제이다.

---

코드

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main_11286 {
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        StringBuilder sb = new StringBuilder();

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new 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 if (Math.abs(o1) == Math.abs(o2)) {
                    return o1 - o2;
                } else return -1;
            }
        });

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if (x == 0) {
                if (pq.isEmpty()) {
                    sb.append("0").append('\n');
                } else {
                    sb.append(pq.poll()).append('\n');
                }
            } else {
                pq.offer(x);
            }
        }
        
        System.out.println(sb);
        
    }
}

---

코드 설명

절댓값 힙에서 요구하는 연산은 두가지이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

이 두가지 조건에 맞게 우선순위 큐를 구현하면 된다.

이 문제에서 중요한 부분인 2번 조건은 다음과 같이 구현했다.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new 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 if (Math.abs(o1) == Math.abs(o2)) {
			return o1 - o2;
		} else return -1;
	}
});

java.util.Comparotor 를 이용하여 구현하였고 절댓값을 비교하여 가장 작은 값부터 출력하고 만약 절댓값이 같다면 더 작은수를 return 할 수 있도록 하였다.