[Algorithm] 백준 11286번 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

오늘 오전에는 BaekJoon의 우선순위 큐 문제를 풀어보았습니다. 이번 포스팅은 우선순위 큐의 정의, Comparable - comparator

백준 11286번 문제 해결 과정을 정리하도록 하겠습니다.

 

문제 출처: https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

1. Priority Queue의 특징

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조
• 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있습니다.
• 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(nlogn)
• PriorityQueue에 객체를 추가하는 방법은 아래 표와 같습니다.

	예외 발생	값 리턴
추가	add	offer (큐가 가득찬 경우 추가 실패 -> false)
삭제	remove	poll
rjatk	element	peek

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

2 자료 구조 힙이란?

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 구조입니다.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조입니다.

힙은 반정렬(느슨한 정렬 상태)을 유지합니다.

-> 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리입니다. 힙 트리는 중복된 값을 허용합니다.

 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

자바 PriorityQueue에서 Heap 구현하기

자바는 PriorityQueue를 구현하기 위해 라이브러리를 호출해야 합니다. 만약 기본 타입이나, Wrapper 변수의 경우, 기본 정렬 방식을 사용할 수 있지만, 사용자 정의 클래스 객체에 우선순위 큐를 적용하기 위해서는 비교(정렬) 방식을 정의해야 합니다. 따라서, 해당 문제에서는 Comparable 인터페이스를 구현하였습니다.

 

import java.util.PriorityQueue

 

Comparable과 Comparator 차이점

 

아래 블로그에 두 클래스에 대한 차이점을 명확하게 설명되어 있어서 참조 링크를 남기겠습니다.

요약하면, Comparable은 자기 자신과 매개변수 객체를 비교하는 것이고,

Comparator는 매개변수로 들어오는 두 객체를 비교하는 것입니다.

참조: https://st-lab.tistory.com/243

 

3. 문제 풀이

해당 문제는 절댓값 힙을 이용하여 입력값이 0인 경우, 절댓값이 가장 작은 값을 출력하고, x 이외의 숫자가 입력되면 힙에 추가하는 방식을 구현하는 문제입니다.

 

저는 위에 정리한 PriorityQueue와 Comparable 인터페이스를 구현하는 방법과 Comparator를 람다식으로 활용하여 해당 문제를 해결하였습니다. 특이점은,

AbsNumber 객체는 절댓값 힙 내에서만 사용되는 객체라 판단하였고, 해당 필드를 Main 클래스 내에서 사용하기 위하여 static 클래스로 선언하였습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;


public class Main {

    static class AbsNumber implements Comparable<AbsNumber>{
        private int num;

        public AbsNumber (int num) {
            this.num = num;
        }

        @Override
        public int compareTo(AbsNumber absNumber) {

            if (Math.abs(this.num) == Math.abs(absNumber.num)) {
                return Integer.compare(this.num, absNumber.num);
            }
            return Integer.compare(Math.abs(this.num), Math.abs(absNumber.num));
        }
    }

    public static void main(String[] args) throws IOException {

        PriorityQueue<AbsNumber> absHeap = new PriorityQueue<>();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(reader.readLine());

            if (x == 0) {
                if (absHeap.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(absHeap.poll().num);
                }
            } else {
                absHeap.add(new AbsNumber(x));
            }
        }
    }

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;


public class Main11286_2 {

    static class AbsNumber {
        private int num;

        public AbsNumber (int num) {
            this.num = num;
        }
    }

    public static void main(String[] args) throws IOException {

        PriorityQueue<AbsNumber> absHeap = new PriorityQueue<>(
                (absNumber, t1) -> {

                    if (Math.abs(absNumber.num) == Math.abs(t1.num)) {
                        return absNumber.num - t1.num;
                    }
                    return Math.abs(absNumber.num) - Math.abs(t1.num);
                }
        );

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(reader.readLine());

            if (x == 0) {
                if (absHeap.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(absHeap.poll().num);
                }
            } else {
                absHeap.add(new AbsNumber(x));
            }
        }
    }

}

두 해결방식의 차이점은 AbsNumber라는 객체를 객체 중심적으로 보고 해결하느냐, 혹은 해당 알고리즘에 특화된 객체라고 판단하고 해결하는가? 두 의도에 따라 달라진다고 생각합니다.

 

전자는. 내부 클래스에 선언했으므로 해당 AbsNumber를 이 과제에 특화되어 사용되는 클래스라고 판단하였기 때문에, Comparable 인터페이스를 구현하였습니다.

 

후자는, AbsNumber를 Comparable을 구현한 클래스로 만들면,  AbsNumber가 정렬 방식에 의존하게 된다는 생각이 들었습니다.  따라서, AbsNumber는 '절댓값의 수'라는 본질의 객체를 남겨두고,  과제를 해결하는 메소드 내에서 PriorityQueue에 사용할 정렬 방식을 Comparator<AbsNumber> 익명 내부 클래스 -> 람다로 전환하여 사용하였습니다.

 

감사합니다.!