[정글 알고리즘] - [상] -백준 1655번 골드 II - 큐_가운데를말해요_

 

 

숫자를 하나씩 입력받을 때마다 지금까지 입력된 수들의 중앙값을 즉시 출력하는 문제입니다.
단순 정렬로도 풀 수 있지만 N = 100,000에서는 시간초과가 발생합니다.
핵심 아이디어: 두 개의 힙(최대 힙 + 최소 힙)을 사용하여 O(log N)에 중앙값을 유지합니다.

📋 문제 정보

항목	내용
문제 번호	백준 1655번
난이도	🟡 골드 II
알고리즘	우선순위 큐 (힙), 두 힙 기법
입력	첫째 줄: 정수 개수 N (1 ≤ N ≤ 100,000) 이후 N줄: 정수 (−10,000 이상 10,000 이하)
출력	N줄: 각 숫자가 추가될 때마다 중앙값 출력 (짝수 개면 두 중간값 중 작은 값)
예제 입력	1 → 5 → 2 → 10 → -99 → 7 → 5
예제 출력	1 → 1 → 2 → 2 → 2 → 2 → 5

❌ 왜 단순 정렬은 안 되는가?

방법 1: 매 삽입마다 list.sort() 호출

lst = []
for _ in range(n):
    x = int(input())
    lst.append(x)
    lst.sort()           # ← 매번 O(N log N)
    print(lst[(len(lst)-1)//2])

문제점	설명
lst.sort (괄호 없음)	정렬 함수를 참조만 하고 실행하지 않음 → 정렬 안 됨
len(input())	입력 문자열의 길이를 저장 (숫자 값이 아님)
시간복잡도	N번 × O(N log N) = O(N² log N) → N=100,000에서 TLE

📐 중앙값 인덱스 공식

정렬된 리스트에서 중앙값의 인덱스: (len(lst) - 1) // 2

원소 개수	공식 결과	예시 (정렬된 리스트)	중앙값
1개	(1-1)//2 = 0	[3]	3
2개	(2-1)//2 = 0	[1, 5]	1 (작은 쪽)
3개	(3-1)//2 = 1	[1, 2, 5]	2
4개	(4-1)//2 = 1	[1, 2, 5, 10]	2 (작은 쪽)

💡 핵심 아이디어: 두 힙 구조

전체 숫자를 작은 절반과 큰 절반으로 나눠 두 개의 힙에 저장합니다.

힙	종류	저장 대상	루트(top)	Python 구현
left (왼쪽)	최대 힙	작은 절반의 수들	작은 절반 중 최댓값	heapq + 음수 저장
right (오른쪽)	최소 힙	큰 절반의 수들	큰 절반 중 최솟값	heapq 기본 사용

✅ 불변 조건 (Invariant)

① len(left) == len(right)  또는  len(left) == len(right) + 1
(left가 항상 같거나 1개 더 많음)

② max(left) ≤ min(right)
(왼쪽 최댓값 ≤ 오른쪽 최솟값)

③ 중앙값 = left의 루트 = -left[0]

🔍 두 힙 구조 시각화

예: 수열 [1, 5, 2, 10, -99]가 모두 입력된 후 상태 (정렬: [-99, 1, 2, 5, 10])

left (최대 힙)
작은 절반 저장

2 ← 루트 (중앙값!)
1
-99

내부 저장: [-2, -1, 99]
(음수로 저장)

⟷

right (최소 힙)
큰 절반 저장

5 ← 루트
10

내부 저장: [5, 10]
(그대로 저장)

전체 정렬 기준: [-99, 1,  2 , 5, 10]
↑ 인덱스 (5-1)//2 = 2 번째 → 중앙값 = 2
✓ left 루트(-left[0] = 2)와 일치!

⚙️ 삽입 로직 단계별 설명

단계	조건	동작
①	항상	새 수 x를 left(최대 힙)에 삽입: heappush(left, -x)
②	len(left) > len(right) + 1	left가 너무 큼 → left의 루트를 꺼내 right로 이동 heappush(right, -heappop(left))
③	left[0] < -right[0] (= max(left) > min(right))	순서 역전 → 서로 루트를 교환 heappush(left, -heappop(right)) heappush(right, -heappop(left))
④	항상 (출력)	중앙값 = -left[0] 출력

🎬 단계별 시뮬레이션 (입력: 1 5 2 10 -99 7 5)

입력	동작	left (최대 힙) 음수 저장 → 실제 값	right (최소 힙)	left 크기	right 크기	출력 (중앙값)
1	① left에 1 삽입	[1]	[ ]	1	0	1
5	① left에 5 삽입 ② left 크기(2) > right+1(1) → left 루트(5)를 right로	[1]	[5]	1	1	1
2	① left에 2 삽입 → left=[2,1] 크기 균형 OK, 순서 OK	[2], 1	[5]	2	1	2
10	① left에 10 삽입 → left=[10,1,2] ② left 크기(3) > right+1(2) → 루트(10)을 right로	[2], 1	[5, 10]	2	2	2
-99	① left에 -99 삽입 → left=[2,1,-99] 크기 균형 OK (3 == 2+1), 순서 OK	[2], 1, -99	[5, 10]	3	2	2
7	① left에 7 삽입 → left=[7,1,-99,2] ② left 크기(4) > right+1(3) → 루트(7)을 right로	[2], 1, -99	[5, 10, 7]	3	3	2
5	① left에 5 삽입 → left=[5,2,-99,1] 크기 균형 OK (4 == 3+1), 순서 OK	[5], 2, -99, 1	[5, 10, 7]	4	3	5

✅ 최종 출력: 1 1 2 2 2 2 5 → 예제 정답과 일치!

🐍 Python heapq와 최대 힙 구현

Python의 heapq는 기본적으로 최소 힙만 지원합니다.

문제	해결법
최대 힙이 필요할 때	값을 음수(-x)로 저장하고, 꺼낼 때 다시 음수로 변환
heappush(left, -x)	x를 최대 힙에 삽입
-left[0]	최대 힙의 최댓값 확인 (꺼내지 않음)
-heappop(left)	최대 힙에서 최댓값을 꺼냄

import heapq

heap = []                          # 최대 힙으로 사용할 리스트

heapq.heappush(heap, -5)           # 5 삽입
heapq.heappush(heap, -3)           # 3 삽입
heapq.heappush(heap, -8)           # 8 삽입

print(-heap[0])                    # 최댓값 조회: 8
print(-heapq.heappop(heap))        # 최댓값 제거 및 반환: 8
print(-heap[0])                    # 다음 최댓값: 5

✅ 최종 풀이 코드 (주석 포함)

import sys
import heapq

# 빠른 입력
input = sys.stdin.readline

n = int(input())

left  = []  # 최대 힙: 작은 절반 저장 (음수로 저장)
right = []  # 최소 힙: 큰  절반 저장
result = []

for _ in range(n):
    x = int(input())

    # ① 새 수를 left(최대 힙)에 삽입
    heapq.heappush(left, -x)

    # ② 크기 균형: left가 right보다 2개 이상 많으면 left 루트를 right로
    if len(left) > len(right) + 1:
        heapq.heappush(right, -heapq.heappop(left))

    # ③ 순서 유지: left 최댓값 > right 최솟값이면 교환
    if right and left[0] < -right[0]:   # left[0]은 음수 → left[0] < -right[0]
        heapq.heappush(left,  -heapq.heappop(right))
        heapq.heappush(right, -heapq.heappop(left))

    # ④ 중앙값 = left의 루트 (음수이므로 -를 붙임)
    result.append(-left[0])

# 출력은 한 번에 (sys.stdout.write가 print보다 빠름)
print("\n".join(map(str, result)))

🔎 코드 핵심 라인 해설

코드	설명
heapq.heappush(left, -x)	x를 음수로 저장 → 최소 힙이 최대 힙처럼 작동
len(left) > len(right) + 1	left가 right보다 2개 이상 많은 경우 균형 필요
left[0] < -right[0]	left[0]은 음수(ex: -5), -right[0]도 음수(ex: -3) -5 < -3 → left 최댓값(5) > right 최솟값(3) 의미
-left[0]	left 루트(음수)에 -를 붙여 실제 중앙값으로 변환
"\n".join(map(str, result))	결과 리스트를 한 번에 출력 (반복 print보다 빠름)

⚠️ 조건 ③ 심화: left[0] < -right[0] 이해하기

이 조건이 헷갈리는 이유는 left에는 음수, right에는 양수가 저장되기 때문입니다.

상황	left[0]	right[0]	-right[0]	left[0] < -right[0]	의미
정상	-2	5	-5	-2 < -5? False	max(left)=2 ≤ min(right)=5 → OK
역전!	-7	3	-3	-7 < -3? True	max(left)=7 > min(right)=3 → 교환 필요!

⏱️ 시간복잡도 분석

방법	1회 연산	전체 (N=100,000)	결과
매 삽입마다 sort()	O(N log N)	O(N² log N)	❌ TLE
두 힙 사용	O(log N)	O(N log N)	✅ 통과

🚨 자주 하는 실수 TOP 3

순위	실수	올바른 코드
1	lst.sort → 함수 참조만 하고 실행 안 됨	lst.sort() 괄호 필수!
2	len(input()) → 문자열 길이를 저장	int(input()) 정수로 변환 필수!
3	if right and ... 없이 right[0] 접근 → IndexError	if right and left[0] < -right[0]:

🏁 핵심 정리

포인트	내용
💡	두 힙으로 수열을 작은 절반 / 큰 절반으로 분리 유지
📏	항상 left 크기 ≥ right 크기 (최대 1개 더 많게)
🔢	중앙값은 항상 left의 루트 = -left[0]
🐍	Python 최대 힙 = heapq + 음수 저장
⏱️	시간복잡도 O(N log N) → N=100,000도 안전하게 통과