[백준, 11286번] 절댓값 힙 (우선 순위 큐, 정렬, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 절댓값 힙" 문제는 우선순위 큐 자료구조를 사용하여 풀이한다면 손쉽게 풀이할 수 있는 문제입니다.

[자료구조 JAVA] 우선순위 큐(Priority Queue) 클래스 알아보기 ✔

 

선순위 큐는 일반적으로 힙(heap)이라는 트리 구조를 기반으로 구현됩니다. 이 힙에 정수x를 넣고 0이 입력될 때마다 힙에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거합니다.

 

만약 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하는 문제입니다.

요구사항을 만족하기 위해서는 Comparator를 사용하여 커스텀 정렬을 구현해야합니다.

 

---

전체 코드 

 

이번 문제의 핵심인 Comparator를 사용한 커스텀 정렬을 주로 설명해보겠습니다.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a,b) -> {
           int absA = Math.abs(a);
           int absB = Math.abs(b);

           if(absA == absB) return Integer.compare(a,b);

           return Integer.compare(absA,absB);
        });

 

요구사항 1 : 절댓값이 가장 작은 값을 출력

return Integer.compare(absA,absB);  // 절댓값 기준 정렬

 

• Math.abs()메서드로 절댓값을 구하고
• Integer.compare(absA,absB)로 절댓값이 작은 값이 우선순위가 높도록 정렬

 

요구사항 2 : 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력

if(absA == absB) return Integer.compare(a,b);

• 절댓값이 같을 때(absA == absB)
• 원래 값을 비교(Integer.compare(a,b))하여 더 작은 값이 우선순위가 높도록 정렬

 

정렬 동작 원리

Comparator의 반환 값에 따라서 동작은 다음과 같이 진행됩니다.

// 모든 경우에서
양수 반환 → 순서 바꿈
음수 반환 → 순서 유지
0 반환 → 동일 값

---

Integer.compare(absA,absB)

• absA가 더 크면 양수가 반환되어 순서가 바뀌어 절대값이 작은 값이 앞으로 감
• absA가 더 작으면 음수가 반환되어 순서가 유지되어 절대값이 작은 값이 앞에 있게 됨
• 절대값이 같으면 0이 반환되어 동일한 값으로 취급

즉, 이 비교 로직과 우선순위 큐의 최소 힙 특성이 함께 작용하여 결과적으로 절대값이 작은 값이 큐의 맨 앞에 위치하게 됩니다.

---

// 절대값 오름차순(작은 값 우선)
return Integer.compare(absA, absB);  // absA가 크면 양수->순서바꿈

// 절대값 내림차순(큰 값 우선)
return Integer.compare(absB, absA);  // absB가 크면 양수->순서바꿈

 

만약 PriorityQueue가 최대 힙을 기본으로 했다면, 절댓값이 큰 수가 먼저 나오도록 하기 위해 Integer.compare(absB, absA)와 같이 비교 순서를 반대로 해야합니다.

결국 중요한 것은 첫 번째 파라미터가 두 번째 파라미터보다 크면 순서가 바뀐다는 것입니다.

---

1. 오름차순 정렬을 원할 때: Integer.compare(absA, absB)

예1) absA=5, absB=3 일 때
compare(5,3) → 양수 반환 → 순서 바꿈 → [3,5]
// 5가 3보다 크므로, 순서를 바꿔서 작은 값이 앞으로

예2) absA=2, absB=4 일 때
compare(2,4) → 음수 반환 → 순서 유지 → [2,4]
// 2가 4보다 작으므로, 순서 유지해서 작은 값이 앞으로

 

2. 내림차순 정렬을 원할 때: Integer.compare(absB, absA)

예1) absA=5, absB=3 일 때
compare(3,5) → 음수 반환 → 순서 유지 → [5,3]
// 3이 5보다 작으므로, 순서 유지해서 큰 값이 앞으로

예2) absA=2, absB=4 일 때
compare(4,2) → 양수 반환 → 순서 바꿈 → [4,2]
// 4가 2보다 크므로, 순서를 바꿔서 큰 값이 앞으로

 

쉽게 말해서 오름차순 정렬을 위해 a를 앞에 두었다고 이해하면 좋습니다!