문제 소개 (백준 2075번)

N x N 크기의 행렬이 주어지고, 각 행은 한 줄씩 입력으로 주어집니다. 이 행렬에서 N번째로 큰 수를 찾는 문제입니다. 단순히 모든 수를 정렬하면 될 것 같지만, 다음과 같은 제약 조건이 있습니다.

  • N: 최대 1500
  • 메모리 제한: 12MB

흔한 실수와 메모리 초과

많은 분들이 처음 시도하는 방법은 모든 수를 리스트에 담고, 내림차순 정렬 후 N-1번째 요소를 출력하는 것입니다.

# 메모리 초과 (Memory Limit Exceeded) 발생!
n = int(input())
arr = []
for _ in range(n):
    arr.extend(list(map(int, input().split())))

arr.sort(reverse=True)
print(arr[n - 1])

얼핏 보면 메모리 제한 내에 들어올 것 같지만, 이 코드는 메모리 초과로 실패합니다. N=1500일 때, arr 리스트는 2,250,000개의 정수를 저장하며, 약 9MB를 차지합니다. 문제는 파이썬의 list.sort() (Timsort 알고리즘)가 정렬 과정에서 추가적인 메모리를 최대 O(N)만큼 사용한다는 점입니다. 따라서 정렬 시 거의 두 배의 메모리를 사용하게 되어 12MB 제한을 넘어서게 됩니다.

해결 전략: 최소 힙(Min-Heap)

핵심은 모든 수를 저장하지 않는 것입니다. 우리는 N번째로 큰 수만 알면 됩니다. 이를 위해 크기가 N인 최소 힙(min-heap)을 사용합니다. 최소 힙은 항상 가장 작은 원소가 루트에 위치하는 자료구조입니다.

import heapq

n = int(input())
heap = []

for _ in range(n):
    row = list(map(int, input().split()))
    for x in row:
        if len(heap) < n:
            heapq.heappush(heap, x)  # 힙이 N보다 작으면 그냥 추가
        else:
            if x > heap[0]:  # 힙의 루트(최솟값)보다 크면
                heapq.heapreplace(heap, x)  # 루트를 제거하고 새 원소 삽입

print(heap[0])  # 힙의 루트가 N번째로 큰 수

동작 원리:

  1. heapq 모듈: 파이썬의 heapq 모듈을 사용하여 최소 힙을 구현합니다.
  2. 크기 N 유지:
    • 힙의 크기가 N보다 작으면, 입력받은 수를 heapq.heappush로 힙에 추가합니다.
    • 힙의 크기가 N이면, 입력받은 수 x를 힙의 루트(heap[0], 최솟값)와 비교합니다.
    • x가 heap[0]보다 크면, heap[0]은 N번째 큰 수가 될 수 없으므로 제거하고, x를 힙에 넣습니다. heapq.heapreplace는 이 과정을 효율적으로 수행합니다(pop 후 push보다 빠름).
  3. 결과: 모든 수를 처리한 후, 힙에는 가장 큰 N개의 수가 남아있고, 그중 가장 작은 수(힙의 루트)가 N번째로 큰 수가 됩니다.

시간/공간 복잡도:

  • 시간 복잡도: O(N² log N). heappush와 heapreplace는 O(log N)이고, N*N개의 원소에 대해 수행합니다.
  • 공간 복잡도: O(N). 힙의 크기는 N으로 일정합니다.

결론

백준 2075번 문제는 메모리 제한 때문에 단순한 정렬로는 풀 수 없습니다. 최소 힙을 사용하여 가장 큰 N개의 수만 유지하는 것이 핵심 전략입니다. 이 문제는 자료구조의 선택이 얼마나 중요한지를 잘 보여줍니다.