[백준] 1655번 - 가운데를 말해요 문제 풀이 및 코드 해석 (Python)

1. 문제 분석

📌 문제 개요

• 숫자가 순차적으로 입력되며, 매 순간마다 중간값을 출력해야 한다.
• 입력된 숫자의 개수가 짝수라면 두 수 중 작은 수를 출력해야 한다.
• 정렬을 수행하면 O(N log N)이 걸리므로, Heap을 이용하여 O(log N)으로 해결해야 한다.

🎯 요구사항

1. 매 순간마다 중간값을 빠르게 찾아야 한다.
2. 정렬된 상태를 유지하면서도 효율적으로 삽입이 가능해야 한다.
3. 중간값을 즉시 출력해야 한다.

---

2. 해결 방법

🔹 핵심 개념

• "중간값을 빠르게 찾는 문제" → Heap(우선순위 큐) 활용!
• 두 개의 힙(Heap)을 활용하여 정렬된 상태를 유지하면서 중간값을 찾는다.
• Python의 heapq는 기본적으로 최소 힙(Min-Heap)이므로, 최대 힙을 만들기 위해 음수 값을 저장한다.

🔑 해결 절차

1. 두 개의 힙을 사용하여 값을 정렬된 상태로 유지한다.

   • 최대 힙 (leftheap): 중간값 이하의 숫자들을 저장 (최대값이 루트)
   • 최소 힙 (rightheap): 중간값 이상의 숫자들을 저장 (최소값이 루트)

2. 삽입 규칙

   • 숫자를 leftheap에 우선 삽입 (최대 힙이 중간값을 포함해야 함)
   • 두 힙의 크기 조정: leftheap의 크기는 rightheap보다 같거나 하나 더 커야 한다.
   • 값 교환: leftheap의 최대값이 rightheap의 최소값보다 크다면 교환

3. 중간값 출력

   • 항상 leftheap[0]의 음수 값을 출력하면 된다.

---

3. 코드 구현 (Python)

import heapq
import sys

input = sys.stdin.readline

N = int(input())

leftheap = []  # 최대 힙 (중간값 이하의 값 저장)
rightheap = []  # 최소 힙 (중간값 초과의 값 저장)

for _ in range(N):
    num = int(input())

    # 1. leftheap에 먼저 삽입 (음수로 넣어 최대 힙처럼 동작)
    if len(leftheap) == len(rightheap):
        heapq.heappush(leftheap, -num)
    else:
        heapq.heappush(rightheap, num)

    # 2. leftheap(최대 힙) 값이 rightheap(최소 힙) 값보다 크면 교환
    if rightheap and -leftheap[0] > rightheap[0]:
        l = -heapq.heappop(leftheap)
        r = heapq.heappop(rightheap)

        heapq.heappush(leftheap, -r)
        heapq.heappush(rightheap, l)

    # 3. 중간값 출력
    print(-leftheap[0])

---

4. 코드 분석

🔹 주요 알고리즘

1. 최대 힙(leftheap)과 최소 힙(rightheap) 사용

   • leftheap: 중간값 이하의 값 저장 (최대 힙)
   • rightheap: 중간값 초과의 값 저장 (최소 힙)
   • leftheap의 최대값이 중간값이 되도록 유지

2. 힙 균형 유지 및 값 교환

   • leftheap의 크기는 rightheap보다 크거나 같아야 한다.
   • leftheap[0]이 rightheap[0]보다 크다면 값을 교환하여 정렬 상태 유지

3. 중간값 출력

   • 항상 leftheap[0]이 중간값이므로 출력

---

5. 시간 복잡도 분석

• 삽입 연산 (heapq.heappush) → O(log N)
• 삭제 연산 (heapq.heappop) → O(log N)
• 총 연산 횟수: O(N log N)
• 최대 입력 크기 (N = 100,000)에서도 충분히 빠르게 동작

---

6. 개선할 점 및 대체 방법

✅ 개선할 점

1. 힙을 사용하지 않고 정렬된 리스트를 유지하면서 삽입할 수도 있지만, O(N log N)보다 느려질 가능성이 높다.
2. 데이터의 범위가 작다면 bucket을 활용한 카운팅 정렬 방식도 고려할 수 있다.
3. Java에서는 PriorityQueue를 사용하여 Collections.reverseOrder()로 최대 힙을 구현할 수 있다.

🔄 대체 방법

1. Ordered Set을 활용한 중간값 찾기

   • SortedList(Python) 또는 TreeSet(Java)를 활용하여 중간값을 찾는 방식도 가능
   • 하지만 삽입이 O(log N)이라서 성능이 비슷하다.

2. 정렬을 유지하면서 이진 탐색을 활용한 방법

   • bisect을 이용하여 삽입하면 O(N log N), 삭제는 O(N)