[Java] Priority Queue 매개변수에 람다식 쓰는 이유가 뭐야?

Robo·2022년 2월 2일

Compare PriortiyQueue 초보자

BackJoon

목록 보기

1/1

시작하기 전에

Java로 Priority Queue 예제를 풀어보기로 했다. 근데 백준 11286을 푸는데 문제점이 생겼다.

문제를 요약하면 다음과 같다.

0이 아닌 값이 입력되면 입력되라.

0이 입력되면 입력된 값을 출력해라.

다만, 출력될 때 절댓값이 가장 낮은 값부터 출력되지만, 절댓값이 같은게 여러 개라면 음수부터 출력해라.

Priority Queue를 쓰면 간단할 것 같다. 하지만 저 빨간글이 문제였다.

기본적으로 제공되는 Priority Queue는 제일 작은 수가 맨 앞부터 배열된다. 어떻게 하면 절댓값으로 배열 후, 음수가 양수보다 앞쪽에 위치할 수 있을까?

많은 블로그들에서 해답으로 람다식 사용을 제공한다.

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
	int abs1 = Math.abs(o1);
	int abs2 = Math.abs(o2);

	if(abs1 == abs2) return o1 > o2 ? 1 : -1;
	return abs1 - abs2;
});

람다식 왜 쓰는건데? 그리고 람다식을 쓰면 어떻게 되는건데? 하는 분들을 위해 위 글을 쓴다.

람다식 자체를 모른다면 [JAVA] 람다식(Lambda)의 개념 및 사용법을 참조해주길 바란다.

Priority Queue 가 뭔데?

Priority Queue는 힙 구조를 이용해서 만드는데 큰 값이 맨 앞으로 가는 최대힙, 작은 값이 맨 앞으로 가는 최소힙이 있다고 생각하면 된다. 자바는 기본값이 최소힙이다.

Heap과 Priority Queue 자체를 잘 모르겠다면, 우선순위 큐(Priority Queue) 이해하기를 참조해주길 바란다.

본 글에선 Priority Queue 자체를 해설하는게 아니라 "절댓값으로 배열하되, 절댓값이 같다면 음수부터 배열"하는 방법을 알아보는 것이다.

Java에서 PriorityQueue 사용법

최소힙 (숫자 최소값부터 배열)

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

최대힙 (최대값부터 배열)

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

대체로 PriorityQueue를 쓴다면 숫자나 문자형같이 기본형 상수값을 쓰는게 일반적이다. 하지만, Java는 특이하게 객체 형태도 PriorityQueue를 쓸 수 있다.

public class Number{
	boolean minus;
    int value;
    
    public Number(boolean minus, int value){
   		this.minus = minus;
        this.value = value;
  	}
}

만약, 이런 클래스가 존재하고 Number를 PriorityQueue에 넣는 상상을 해보자.

public Main{
	public static void main(String[] args){
    	PriorityQueue<Number> pq = new PriorityQueue<Number>();
        
        pq.add(new Number(true, 1));
        pq.add(new Number(false, 2));
    }
}

이런 형태라면 어떻게 PriorityQueue에서 배열되는걸까? 에라이. 컴퓨터가 똑똑하니까 대충 그냥 배열되겠지하며 실행시켜보자.

실행시켜보면, 물론 컴퓨터도 어떻게 배열시키는지 모른다. 그래서 오류를 발생시킨다.

class queue.Number cannot be cast to class java.lang.Comparable

잘 읽어보면 class queue.Number가 java.lang.Comparable로 변환이 안된다고 뜬다.

궁금증이 두 가지가 든다.

class queue.Number가 뭐냐?
java.lang.Comparable로 왜 형변환을 시키는거지?

1번은 쉽다. queue는 내가 만들어준 패키지였다. queue는 아무 의미 없고 그냥 Number 클래스를 포함한 패키지라고 생각하면 된다.

2번은 Comparable로 형변환을 시키는 이유다. 이건 원래 무조건 한다고 생각하면 된다. 원래 Integer나 Char를 넣어도 비교하기위해 Comparable로 형변환을 시킨다. 다만 오류가 난 까닭은 Number객체를 Comparable로 비교해주지 못했다고 생각하면된다.

비교를 해줘야 Priority Queue 배열을 할 수 있으니까!

Comparable로 변환시키기 위해선 Priority Queue 생성자에 매개변수로 Comparator를 넣어줘야지만 변환할 수 있다. Comparator에 대한 내용은 밑에서 자세히 설명하겠다.

PriorityQueue 배열 순서 커스텀

자, 그럼 이제 Priority Queue에서 절댓값이 같은게 여러 개라면 음수부터 배열해라 라는 커스텀을 어떻게 할 수 있는걸까?

생성자	설명
PriorityQueue(Comparator<? super E> comparator)	Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.

우린, 이걸 써야만 커스텀 할 수 있다고 생각하면 된다. 더 편한 방법을 찾기 힘들다.

위 Comparator이 매개변수로 들어간 이상 Comparator이라는 클래스를 쓰며 배열 순서를 커스텀해야한다.

Comparator은 뭘까?

항상 우리는 공식문서와 가까워야한다. Comparator Java 공식문서

그런데 나는 공식문서를 봐도 잘 이해가 안되서 Comparator class를 뒤져보았다.

주석과 메소드 정의된 부분을 간략화하자면 다음과 같이 구성되어있다.

@FunctionalInterface
public interface Comparator<T> {
	// 선언은 이 둘 뿐이다.
	int compare(T o1, T o2);
	boolean equals(Object obj);

	//(메소드가 정의되어 있다.)
	...
}

람다식을 열심히 봤다면 @FunctionalInterface가 무엇을 의미하는지 알 것이다. 람다식을 쓸 수 있다는 소리다.

다만, 추상 메소드 선언이 하나만 되어있어야하는데 두 개 있어서 당황스럽지 않은가?

이건 매개변수 개수로 분간이 가능하다!

Comparator를 쓰는 방법

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
	int abs1 = Math.abs(o1);
	int abs2 = Math.abs(o2);

	if(abs1 == abs2) return o1 > o2 ? 1 : -1;
	return abs1 - abs2;
});

시작하기 전에 위에서 이런 예를 들었었다. 이제는 이걸 이해할 수 있을 것이다.

// Comparator 부분
Comparator<Integer> comparator = new Comparator<Integer>() {
	@Override
	public int compare(int o1, int o2) {
		int abs1 = Math.abs(o1);
		int abs2 = Math.abs(o2);

		if(abs1 == abs2) return o1 > o2 ? 1 : -1;
		return abs1 - abs2;
	}
};

PriorityQueue<Integer> queue = new PriorityQueue<>(comparator);