CT | 백준 - 11286번 절대값 힙

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

문제 설명

이 문제는 정수들을 입력받아 다음과 같은 두 가지 작업을 수행하는 프로그램을 작성하는 것입니다.

1. 정수 입력: 정수 x를 입력받았을 때, x가 0이 아닌 경우 해당 숫자를 우선순위 큐에 추가합니다.
2. 0 입력: 만약 0이 입력되면, 현재 큐에 있는 수 중에서 절대값이 가장 작은 수를 출력하고 해당 수를 큐에서 제거합니다. 만약 절대값이 동일한 수가 여러 개 있다면, 그 중에서 가장 작은 수를 출력합니다. 큐가 비어있을 경우에는 0을 출력합니다.

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();

    // 우선순위 큐 정의 및 초기화
    PriorityQueue<Integer> a = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            int abs = Integer.compare(Math.abs(o1), Math.abs(o2));
            if(abs == 0) {
                return Integer.compare(o1, o2);
            } else {
                return abs;
            }
        }
    });

    scanner.nextLine();

    // n번 반복하여 입력 처리
    for (int i = 0; i < n; i++) {
        int input = scanner.nextInt();

        if (input == 0) {
            if(a.isEmpty()) {
                System.out.println(0);
            } else {
                System.out.println(a.poll());
            }
        } else {
            a.add(input);
        }
    }

    scanner.close();
}

코드 동작 과정

1. 입력 및 큐 생성:
   • 먼저 n을 입력받아 반복할 횟수를 설정합니다.
   • 그런 다음 PriorityQueue를 생성하는데, 여기서 새로운 Comparator를 사용하여 큐에 있는 숫자들이 절대값 기준으로 정렬되도록 합니다.
2. Comparator 구현:
   • PriorityQueue의 정렬 기준은 Comparator의 compare 메서드를 통해 정의됩니다.
   • 두 숫자의 절대값을 비교하고, 절대값이 같으면 실제 숫자의 크기를 비교하여 오름차순으로 정렬합니다
3. 입력 처리:
   • 반복문을 통해 입력된 숫자들을 처리합니다.
   • 숫자가 0이 아닌 경우 큐에 추가하고, 0이 입력되면 큐에서 절대값이 가장 작은 수를 꺼내 출력합니다.
   • 만약 큐가 비어 있다면 0을 출력합니다.

코드의 핵심 포인트

• 우선순위 큐(PriorityQueue): 이 문제에서 핵심 역할을 하는 자료구조로, 기본적으로 우선순위를 가진 요소들을 효율적으로 관리하고 처리할 수 있게 합니다.
• Comparator를 사용한 정렬: 절대값을 기준으로 숫자들을 정렬하고, 만약 절대값이 동일하면 실제 값의 크기로 정렬하여 문제의 조건을 만족시킵니다.

시간 복잡도

• 각 숫자를 큐에 삽입하거나 제거하는 작업은 O(log n)의 시간 복잡도를 가지므로, 전체 시간 복잡도는 O(n log n)입니다.

결론

이 프로그램은 절대값을 기준으로 수를 관리해야 하는 문제에서 매우 효과적인 해결책을 제공합니다.

PriorityQueue와 Comparator를 잘 활용한 예시로, 큐의 특성을 잘 이해하고 사용한다면 다양한 문제를 효율적으로 해결할 수 있습니다.

1. Comparator와 compare 메서드의 역할

Comparator는 두 객체를 비교하여 그들 사이의 순서를 결정하는 데 사용됩니다.

PriorityQueue는 기본적으로 자연 순서(예: 정수의 경우 오름차순)대로 요소를 정렬하지만,

특정 기준에 따라 우선순위를 지정하고 싶을 때 Comparator를 사용하여 정렬 기준을 커스터마이즈할 수 있습니다.

Comparator 인터페이스는 compare(T o1, T o2)라는 메서드를 구현해야 하며, 이 메서드는 두 객체 o1과 o2를 비교하여 다음의 세 가지 값을 반환합니다:

• 음수(-1): o1이 o2보다 앞에 위치해야 함을 의미합니다.
• 0: o1과 o2가 동일한 순서를 가져야 함을 의미합니다.
• 양수(1): o1이 o2보다 뒤에 위치해야 함을 의미합니다.

2. PriorityQueue에서 Comparator의 역할

PriorityQueue는 내부적으로 Comparator의 compare 메서드를 사용하여 큐에 있는 요소들의 우선순위를 결정합니다.

예제 코드에서는 우선순위를 절대값을 기준으로 하며, 절대값이 같을 경우 숫자 자체의 크기를 기준으로 정렬합니다.

3. 코드의 Comparator 구현

코드에서 Comparator는 익명 클래스 또는 람다식으로 구현되어 있습니다. 이 Comparator는 두 숫자 o1과 o2를 비교하여 정렬 순서를 결정합니다.

PriorityQueue<Integer> a = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        // 절대값 비교
        int abs = Integer.compare(Math.abs(o1), Math.abs(o2));
        
        if(abs == 0) {
            // 절대값이 같으면 숫자 크기 비교
            return Integer.compare(o1, o2);
        } else {
            return abs;
        }
    }
});