[백준] 1655번 - 가운데를 말해요

1. 문제 요약

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

 

정수를 하나씩 입력받을 때마다
지금까지 들어온 값들의 중간값을 출력하는 문제

• 홀수 개 → 정확한 중앙값
• 짝수 개 → 중앙 두 값 중 작은 값

---

2. 처음 접근 (실패)

이렇게 생각했다.

힙 두 개 쓰면 되지 않을까?

• min_heap (최소 힙)
• max_heap (최대 힙처럼 사용, 음수 저장)

두 개를 만들고 입력값을 각각 넣어서 길이를 맞추려고 했다.

if len(min_heap) > (i+1)//2:
	heapq.heapreplace(min_heap, x)
else:
	heapq.heappush(min_heap, x)

 

max_heap도 처리하고, 중간값은 출력

if i % 2 == 0:
	print(min(min_heap))
else:
	print(-max(max_heap))

 

---

2. 문제점

 1) 두 힙이 “분할 구조”가 아님

이 방식은

• 같은 값이 두 힙에 동시에 들어가고
• 어떤 값은 교체되면서 사라짐

즉,

“작은 값 / 큰 값”으로 나뉜 구조가 아님

---

 2) heapreplace를 잘못 사용

heapreplace는 “루트와 비교해서 교체”할 때 의미가 있는데, 나는 단순히 길이 기준으로 교체했다.

→ 결과: 값의 정렬 정보가 깨짐

---

 3) 힙의 루트를 안 쓰고 전체 탐색

min(min_heap)
max(max_heap)

 

힙의 장점을 완전히 무시한 코드였다.

• 힙은 루트만 보장
• 전체 정렬 아님

→ 무조건 heap[0] 써야 함

---

4. 핵심 깨달음

이 문제의 핵심은 단순히 힙 2개가 아니라

두 힙이 “값의 범위 기준으로 나뉘어야 한다”

---

 올바른 구조

두 힙의 역할은 이렇게 나뉜다.

• max_heap → 작은 값들 (중간값 포함)
• min_heap → 큰 값들

그리고 항상 다음 조건 유지:

max_heap의 모든 값 ≤ min_heap의 모든 값

 

그리고 크기 조건:

len(max_heap) == len(min_heap) 또는
len(max_heap) == len(min_heap) + 1

 

---

5. 중요했던 포인트: swap

가장 헷갈렸던 부분

왜 하나만 옮기지 않고, 두 개를 교환하지?

 1) 의문

 

max_heap → min_heap으로 하나만 보내면 안 되나?

 

---

 2) 안 되는 경우

문제되는 상황:

max_heap: [큰 값이 들어가 있음]
min_heap: [작은 값이 들어가 있음]

 

즉,

→ 경계가 꼬인 상태

---

  한쪽만 이동하면

• 순서가 여전히 깨지거나
• 크기 균형이 깨짐

  3) swap 하여 해결

max_value = -heapq.heappop(max_heap)
min_value = heapq.heappop(min_heap)

heapq.heappush(max_heap, -min_value)
heapq.heappush(min_heap, max_value)

 

효과:

• 잘못된 값 위치를 서로 교환
• 순서 + 크기 동시에 복구

---

 4) 직관

두 힙은 다음과 같이 나뉘어야 한다

[작은 값들 -> max_heap
[큰 값들] -> min_heap

 

잘못되면 [작은 값 + 큰 값] | [작은 값 + 큰 값]과 같이 섞인다

해결 방법:

잘못 들어간 두 값을 서로 교환

---

6. 최종 코드

import heapq
import sys
input = sys.stdin.readline

min_heap = []
max_heap = []
n = int(input())

for _ in range(n):
    x = int(input())
    if len(max_heap) == len(min_heap):
        heapq.heappush(max_heap, -x)
    else:
        heapq.heappush(min_heap, x)

    if min_heap and -min_heap[0] > max_heap[0]:
        max_value = -heapq.heappop(max_heap)
        min_value = heapq.heappop(min_heap)

        heapq.heappush(max_heap, -min_value)
        heapq.heappush(min_heap, max_value)

    print(-max_heap[0])

---

7. 시간 복잡도

• 삽입: O(log N)
• 총: O(N log N)

→ N = 100,000까지 안정적으로 통과