[JAVA] 11286번 절댓값 힙 🩶1 : 시간초과...💥 우선순위 큐(Priority Queue)가 뭔데..?

들어가며

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

문제는 간단하게 정리하자면 입력값에 대해 절댓값이 작은 순서대로 출력하는 것이다.(절댓값이 같은 경우는 음수를 우선으로 한다.)

문제를 딱 읽자마자 든 생각은 이중포문으로 정렬하기 -> ArrayDeque를 이용한 정렬방식이었다..! 

내가 그린 Deque ㅎㅎ..

하지만 코드는 if, while문 덕지덕지가 되어가고... 가장 큰 문제는 시간초과였다. 내가 알고있는 그 어떤 정렬방식, 자료구조를 써봐도 시간초과를 벗어날 수가 없었다(입력 수는 10만이었다.. O(N^2)을 벗어나지 못하면 시간복잡도가 터지는 상황이었다.). 2시간쯤 되었을 때 결국 답지를 봤다. 코드가 매우짧았다. 그곳에선 우선순위 큐(Priority Queue)를 적용하고 있었다.

값을 추가할 때마다 정해진 우선순위를 기반으로 정렬한다는 것은 알고 있었는데, 문제에는 처음 적용해본다.

---

우선순위 큐(PriorityQueue)를 처음 접했을 때 가장 궁금했던 점은 이것이었다.

“어차피 넣을 때마다 정렬하려는 아이디어는 똑같은데,
deque로 직접 구현하면 시간초과가 나고
PriorityQueue는 왜 멀쩡히 통과할까?”

이 글에서는 그 이유를 자료구조 관점 + 알고리즘 관점에서 차분히 정리해본다.

본문으로

1️⃣ deque로 “정렬된 상태 유지”를 흉내내면 왜 느릴까?

deque로 우선순위 큐를 흉내낼 때의 사고 흐름은 대략 이렇다.

• 새 원소가 들어오면
• 앞이나 뒤에서 비교하며
• 적절한 위치를 찾아 삽입
• 항상 “정렬된 상태”를 유지

문제는 이 과정이 선형 구조라는 점이다.

• 최악의 경우 삽입 1회에 O(N)
• N번 삽입하면 O(N²)

입력 크기가 커지면 이 방식은 구조적으로 시간초과가 날 수밖에 없다.

---

2️⃣ PriorityQueue는 “정렬”을 하지 않는다 (뭐?!)

PriorityQueue는 정렬된 리스트가 아니다. Java의 PriorityQueue는 내부적으로 이진 힙(Binary Heap) 을 사용한다.

핵심은 이것이다.

전체를 정렬하지 않고,
“부모 ≤ 자식” 관계만 유지한다.

즉,

• 모든 원소가 순서대로 정렬되어 있을 필요 ❌
• 최솟값(또는 최댓값) 만 빠르게 꺼낼 수 있으면 ⭕️

---

3️⃣ 이진 힙(Binary Heap)의 핵심 특징

Binary Heap은 다음 조건을 만족한다.

1. 완전 이진 트리
2. 부모 노드는 항상 자식 노드보다 우선순위가 높음
3. 트리 높이는 log₂N
4. 배열로 구현 가능

이 구조 덕분에 핵심 연산의 시간복잡도는 다음과 같다.

삽입 (offer)	O(log N)
삭제 (poll)	O(log N)
최솟값 조회 (peek)	O(1)
특정 값 탐색	O(N)

여기서 중요한 점은 삽입/삭제 시에만 트리 높이만큼 이동한다는 것이다...!!!

---

4️⃣ 왜 삽입/삭제가 log N 인가?

힙에 원소를 삽입할 때의 흐름은 이렇다.

1. 배열의 맨 끝에 일단 삽입
2. 부모와 비교
3. 우선순위가 더 높으면 swap
4. 위로 “떠오르기(sift-up)”

이 과정에서 이동하는 최대 횟수는 트리의 높이, 즉 log₂N이다. 삭제도 마찬가지다.

• 루트 제거
• 마지막 원소를 루트로 이동
• 자식과 비교하며 아래로 내리기(sift-down)
• 역시 최대 이동 횟수는 log₂N

---

5️⃣ Comparator는 어떤 상황에서 쓰이는 걸까?

정답 코드의 핵심인 우선순위큐 정렬로직은 아래와 같다. 이 우선순위 큐에 정렬 기준으로 Comparator를 넘겨 우선순위 기준을 설정해줄 수가 있다.

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
            int first_abs = Math.abs(o1);
            int second_abs = Math.abs(o2);
            if(first_abs == second_abs){
                return o1> o2? 1 : -1;
            }
            else{
                return first_abs - second_abs;
            }
        });

 

처음에는 이 기준에 따라 들어올 때마다 모두 다 정렬을 새로하는 줄 알았다...!(그랬다면 시간복잡도가 O(N^2)이겠지...)

PriorityQueue에 전달한 Comparator는 정렬 전체에 쓰이는 게 아니다. Comparator는 오직 다음 상황에서만 호출된다.

• 부모 ↔ 자식 비교
• swap이 필요한지 판단할 때

“필요한 만큼만 비교한다”

이 점이 deque 방식과의 결정적인 차이다.

---

6️⃣ deque vs PriorityQueue 비교 요약

항목	deque로 흉내	PriorityQueue
내부 구조	선형	완전 이진 트리
정렬 방식	전체 순서 유지	부분 순서(부모-자식)
삽입	O(N)	O(log N)
삭제	O(1) / O(N)	O(log N)
대량 데이터	❌ 시간초과	⭕ 안정적

마무리하며

답지를 보고 음.. 처음에는 우선순위 큐를 쓰면 시간복잡도를 줄일 수 있고,, 정렬시에 엄청 간단하게 생각할 수 있구나! 정도의 코테 기술을 얻은 느낌이었다. 하지만 생각할수록 왜 우선순위큐가 빠른건데! 라는 의문점 때문에 찝찝해서 이 기회에 이렇게 정리한다.

 

PriorityQueue가 빠른 이유는 “트리 구조라서”라기보다 정확히는 다음 때문이다.

완전 이진 트리 기반의 힙 구조를 사용해 삽입/삭제 시 필요한 최소한의 비교만 수행하기 때문이다!

그래서 초과 안나게끔 정렬을 흉내낸 deque는 터지고 PriorityQueue는 살아남았던 것이다. 정렬하면서 넣어야하는 문제들은 슬라이딩 윈도우 혹은 우선순위 큐를 상황에 맞게 잘 떠올려야겠다.