[백준, 11279번] 최대 힙 (우선순위 큐, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 최대 힙" 문제는 최소 힙 문제와 한가지만 틀리고 같은 맥락의 문제입니다. 배열에 자연수 x를 넣고, 0이 입력될 때 배열에서 최대값을 출력하는 문제입니다.

 

시간제한이 1초이기 때문에 내부적으로 힙구조를 사용하여 항상 최댓값 혹은 최솟값을 출력할 수 있는 우선순위 큐를 사용하여 풀이해야 합니다.

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

 

---

예제 입력 1번을 최대 힙 구조로 표현한다면 다음과 같습니다.

 

물론 우선순위 큐는 내부적으로 힙 자료구조를 사용하기 때문에 간단한 옵션으로 최대 힙과 최소 힙을 구성할 수 있습니다.

전체 코드

 

Comparator.reverseOrder()

 

Comparator 클래스의 reverseOrder() 메서드를 사용하여 기본 정렬 기준인 오름차순을 내림차순으로 변경하면, poll() 메서드를 호출할 때 항상 큐에서 최댓값이 제거되도록 동작합니다.

 

이때 주의할 점은 큐가 비어있을 때 poll() 메서드를 호출하면 null이 반환된다는 것입니다. 따라서 isEmpty() 메서드로 큐가 비어있는지 먼저 확인하는 것이 중요합니다.