Python으로 선형 시간에 k번째로 작은 요소 찾기: 최대 힙 활용 가이드

문제 개요

숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 리스트에서 k번째(0부터 시작)로 작은 요소를 찾는 것이 목표입니다. 이 문제는 평균적으로 선형 시간, 즉 O(n)에 가까운 성능으로 해결해야 합니다.

예를 들어 입력이 nums = [6, 4, 9, 3, 1], k = 2라고 가정해 보겠습니다. 리스트를 정렬하면 [1, 3, 4, 6, 9]가 되며, 0번째부터 세었을 때 2번째로 작은 요소는 4입니다.

접근 방식: 최대 힙(Max Heap) 활용

Python의 heapq 모듈은 기본적으로 최소 힙만 제공하지만, 요소에 음수 부호를 붙여 저장하면 최대 힙처럼 동작하도록 만들 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 크기가 k+1인 최대 힙을 유지합니다.
• 새로운 요소가 힙의 최댓값보다 작으면, 최댓값을 제거하고 해당 요소를 삽입합니다.
• 모든 요소를 처리한 후 힙의 루트(최댓값)가 곧 k번째로 작은 요소가 됩니다.

알고리즘 단계

1. 비어 있는 최대 힙 maxHeap을 생성합니다.
2. 인덱스 0부터 k까지의 요소를 힙에 삽입합니다.
3. 인덱스 k+1부터 리스트 끝까지 순회하면서, 현재 요소가 힙의 최댓값보다 작으면 최댓값을 제거한 뒤 현재 요소를 삽입합니다.
4. 마지막으로 힙의 루트 값을 반환합니다.

구현 예시

다음 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

from heapq import heappop, heappush

def solve(nums, k):
    maxHeap = []
    for i in range(k + 1):
        heappush(maxHeap, -nums[i])
    for i in range(k + 1, len(nums)):
        if nums[i] < -maxHeap[0]:
            heappop(maxHeap)
            heappush(maxHeap, -nums[i])
    return -maxHeap[0]

nums = [6, 4, 9, 3, 1]
k = 2
print(solve(nums, k))

실행 결과

입력:

[6, 4, 9, 3, 1], 2

출력:

4

복잡도 분석

• 시간 복잡도: 각 요소마다 힙 연산에 O(log k)가 소요되므로 전체적으로 O(n log k)입니다. k가 n에 비해 작다면 사실상 선형 시간에 가깝게 동작합니다.
• 공간 복잡도: 크기 k+1의 힙만 사용하므로 O(k)입니다.

참고로 엄밀한 의미에서 평균 O(n)을 보장하는 알고리즘이 필요하다면 퀵셀렉트(Quickselect) 기법을 사용할 수 있습니다. 다만 최대 힙 기반 접근 방식은 구현이 간단하고, 데이터가 스트리밍 형태로 들어오는 상황에서도 손쉽게 적용할 수 있다는 장점이 있습니다.