🧮 백준 11286 번 절댓값 힙 알고리즘 문제 해결 방법

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

절댓값 힙은 배열에서 절댓값이 가장 작은 값을 출력하고 제거하는 특수한 자료구조입니다. 절댓값이 같을 경우에는 실제 값이 작은 수를 먼저 출력합니다.

1. 🔍 문제 이해와 분석

1.1. 문제 요구사항

• 절댓값 힙은 일반 힙에서 변형된 자료구조입니다
• 두 가지 연산을 지원합니다:
  – 배열에 정수 x (x ≠ 0) 삽입
  – 배열에서 절댓값이 가장 작은 값 출력 및 제거
• 절댓값이 같은 경우 원본 값이 더 작은 수(음수)를 먼저 처리합니다

1.2. 테스트 케이스 분석

• 처음에 1, -1을 입력 후 0을 입력하면 -1이 출력됩니다
• 둘 다 절댓값이 _1_이지만 -1이 더 작은 값이기 때문입니다
• 빈 배열에서 0을 입력하면 0을 출력합니다

2. 🧩 해결 방법 1: 튜플을 사용한 우선순위 큐

2.1. 접근 방식

• heapq 모듈을 사용하여 최소 힙을 구현합니다
• 튜플 형태인 (절댓값, 원본값)을 힙에 저장합니다
• 튜플 비교 시 첫 번째 요소(절댓값)가 같으면 두 번째 요소(원본값)를 비교합니다

2.2. 알고리즘 구현

import heapq as hq
import sys
input = sys.stdin.readline
n = int(input())
pq = []

for _ in range(n):
    x = int(input())
    if x:
        hq.heappush(pq,(abs(x),x))
    else:
        if pq:
            print(hq.heappop(pq)[1])
        else:
            print(0)

2.3. 작동 원리

• (1,1)과 (1,-1)이 모두 들어있을 때, 튜플 비교에서 첫 요소가 같으므로 두 번째 요소를 비교합니다
• -1이 1보다 작으므로 (1,-1)이 먼저 추출됩니다
• 빈 힙에서 추출 요청 시 0을 출력합니다

3. 🔄 해결 방법 2: 두 개의 힙 사용

3.1. 접근 방식

• 양수 전용 최소 힙(min_heap)과 음수 전용 최대 힙(max_heap)을 따로 관리합니다
• 양수는 그대로 최소 힙에 저장합니다
• 음수는 부호를 바꿔서 최대 힙처럼 동작하도록 구현합니다

3.2. 알고리즘 구현

import heapq as hq
import sys
input = sys.stdin.readline

min_heap = []
max_heap = [] 
for _ in range(int(input())):
  x = int(input())
  if x > 0:
    hq.heappush(min_heap, x)
  elif x < 0:
    hq.heappush(max_heap, -x)
  else:
    if min_heap:
      if max_heap:
        if min_heap[0] < max_heap[0]:
          print(hq.heappop(min_heap))
        else:
          print(-hq.heappop(max_heap))
      else:
        print(hq.heappop(min_heap))
    else:
      if max_heap:
        print(-hq.heappop(max_heap))
      else:
        print(0)

3.3. 작동 원리

• 양수는 최소힙에 저장하면 값이 작은 순으로 정렬됩니다
• 음수는 부호를 바꿔서 최대힙에 저장하면 절댓값이 작은 순으로 정렬됩니다
• 두 힙의 루트 노드를 비교하여 절댓값이 더 작은 값을 선택합니다
• 절댓값이 같으면 음수가 들어있는 최대힙에서 값을 꺼냅니다

4. 🔎 두 방법의 비교

4.1. 첫 번째 방법의 특징

• 구현이 더 간결합니다
• 한 개의 힙만 사용하므로 메모리 관리가 효율적입니다
• 튜플 비교 연산이 추가되어 약간의 오버헤드가 발생할 수 있습니다

4.2. 두 번째 방법의 특징

• 음수와 양수를 별도로 관리하여 직관적입니다
• 분기 처리가 많아 코드가 복잡합니다
• 두 개의 힙을 사용하므로 메모리 사용량이 증가합니다

4.3. 시간복잡도

• 두 방법 모두 힙 연산을 사용하므로 O(NlogN) 시간복잡도를 가집니다
• 실제 수행 시간은 큰 차이가 없습니다

5. 📝 구현 시 주의사항

5.1. 입출력 최적화

• sys.stdin.readline을 사용하여 _10만 개_의 입력을 빠르게 처리해야 합니다
• 입력이 많은 경우 일반 input() 함수 사용 시 시간 초과가 발생할 수 있습니다

5.2. 경계 조건 처리

• 빈 힙에서 추출 요청 시 0을 출력해야 합니다
• 절댓값이 같은 경우 음수를 먼저 처리해야 합니다

Citations:

1. https://ppl-ai-file-upload.s3.amazonaws.com/web/direct-files/attachments/56096911/11abf0a6-ab6d-4d7a-8b38-4bbdb316c272/paste.txt
2. https://www.acmicpc.net/problem/11286