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

가운데를 말해요 문제 바로 가기

풀이 날짜: 2026-03-22

baekjoon 알고리즘 문제 풀이

풀이 코드


import heapq
import sys
input = sys.stdin.readline

n = int(input())

left = []
right = []

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

    if len(left) == len(right):
        heapq.heappush(left, -data)
    else:
        heapq.heappush(right, data)

    if right and -left[0] > right[0]:
        l = -heapq.heappop(left)
        r = heapq.heappop(right)

        heapq.heappush(left, -r)
        heapq.heappush(right, l)

    print(-left[0])

문제 이해하기

이 문제는 정수가 하나씩 입력될 때마다, 지금까지 입력된 값들 중에서 “중간값”을 즉시 출력해야 하는 문제이다. 중간값은 정렬했을 때 가운데 위치한 값이며, 개수가 짝수일 경우 가운데 두 값 중 더 작은 값을 선택한다. 즉, 단순히 한 번 정렬하는 것이 아니라, 입력이 들어올 때마다 실시간으로 중간값을 유지해야 하는 것이 핵심이다.

접근 방법

처음에는 리스트에 값을 추가한 뒤 매번 정렬하여 가운데 값을 출력하는 방식이 떠올랐지만, 이 방법은 매 입력마다 정렬이 필요하므로 시간 초과가 발생한다. 이를 해결하기 위해 “힙 2개”를 사용하는 방식으로 접근하였다. 하나는 작은 값들을 저장하는 최대 힙, 다른 하나는 큰 값들을 저장하는 최소 힙으로 구성하여 데이터를 절반씩 나누고, 중간값이 항상 한쪽 힙의 루트에 위치하도록 했다.

핵심 아이디어 - 힙 구조

왼쪽 힙(left)은 중간값 이하의 값들을 저장하는 최대 힙이고, 오른쪽 힙(right)은 중간값 이상의 값들을 저장하는 최소 힙이다. 파이썬은 최소 힙만 지원하기 때문에 left는 음수 값을 넣어 최대 힙처럼 사용한다. 이때 항상 left의 크기가 right보다 크거나 같도록 유지하여, 중간값을 left의 루트 값으로 바로 출력할 수 있도록 만든다.

값 삽입 규칙

새로운 값이 들어올 때는 두 힙의 크기를 비교하여 삽입 위치를 결정한다. 두 힙의 크기가 같다면 left에 넣고, 다르면 right에 넣는다. 이렇게 하면 항상 left ≥ right 구조가 유지되며, 중간값이 left에 존재하게 된다.

힙 정렬 유지 (swap 필요성)

값을 삽입한 후에는 left의 최대값이 right의 최소값보다 큰 경우가 발생할 수 있다. 이 경우 두 힙의 루트를 서로 교환하여 정렬 조건을 다시 맞춰야 한다. 즉, “left의 값은 항상 right보다 작거나 같아야 한다”는 규칙을 유지하기 위해 swap 과정이 필요하다.

중간값 출력

이 구조에서는 중간값이 항상 left 힙의 루트에 위치하므로, -left[0]을 출력하면 된다. 짝수 개일 경우에도 left가 더 많거나 같도록 유지했기 때문에 자동으로 “가운데 두 값 중 작은 값”이 출력된다.

내가 헷갈렸던 포인트

처음 구현할 때 if -left[0] > right[0]: 조건에서 에러가 발생했는데, 이는 right 힙이 비어있는 상태에서 접근했기 때문이었다. left는 항상 먼저 값이 들어가기 때문에 비어있지 않지만, right는 비어있을 수 있으므로 반드시 if right and … 조건으로 체크해야 한다는 점을 놓쳤다. 이 부분은 힙 문제에서 자주 발생하는 실수였다.

기억해둘 핵심 포인트

힙은 정렬된 구조가 아니라 “최솟값/최댓값만 빠르게 꺼내는 구조”이다
중간값을 빠르게 구하려면 데이터를 반으로 나눠야 한다.
left는 최대 힙(음수), right는 최소 힙으로 사용한다.
항상 len(left) ≥ len(right)를 유지한다.
항상 len(left) ≥ len(right)를 유지한다.
right는 비어있을 수 있으므로 접근 전에 반드시 체크해야 한다.

Vienna sausage