[백준] 2075번 - N번째 큰 수

1. 문제 요약

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

N × N 크기의 표가 주어지고,
각 열은 위에서 아래로 갈수록 값이 증가하는 특징을 가진다.

→ 목표: 전체 수 중 N번째로 큰 값 찾기

---

2. 처음 접근 (실패)

처음에는 단순하게 생각했다.

“전체에서 N번째 큰 수니까 다 넣고 뽑으면 되지 않나?”

그래서 아래처럼 구현했다.

import heapq
import sys
input = sys.stdin.readline

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

for i in range(n):
    row = list(map(int, input().split()))
    for x in row:
        heapq.heappush(heap, -x)

for _ in range(n):
    k = -heapq.heappop(heap)

print(k)

→ 최대 힙처럼 쓰기 위해 -x 사용

---

3. 결과: 메모리 초과

왜 터졌을까?

핵심 원인:

모든 데이터를 힙에 저장했기 때문

---

 메모리 분석

최대 입력:

• N=1500N = 1500
• 총 데이터 수 = N² = 2,250,000

즉, 힙에 들어가는 데이터:

→ 약 225만 개

---

 파이썬에서 더 치명적인 이유

• 파이썬 int는 객체라서 메모리를 많이 먹음
• 리스트 + 힙 구조까지 고려하면

→ 12MB 제한 절대 못 버팀

---

4. 문제의 핵심 깨달음

중요한 질문:

우리가 진짜 필요한 건 모든 값인가?

→ 답: 아님

N번째 큰 수 하나만 필요

---

 해결 아이디어

“전체를 저장하지 말고, 필요한 것만 유지하자”

전략:

• 크기가 N인 최소 힙 유지
• 항상 “큰 값 N개만” 남기기

---

5. 알고리즘

각 숫자 x에 대해

1. 힙 크기 < N → 그냥 넣기
2. 힙 크기 == N
    → x > heap[0] (현재 N번째 큰 값)
        → heap[0] 제거 후 x 삽입
    → 아니면 버림

 

---

 개선 코드

 

import heapq
import sys
input = sys.stdin.readline

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

for _ in range(n):
    row = map(int, input().split())
    for x in row:
        if len(heap) < n:
            heapq.heappush(heap, x)
        else:
            if x > heap[0]:
                heapq.heapreplace(heap, x)

print(heap[0])

 

---

6. 핵심 차이 비교

구분기존 코드개선 코드

힙 크기	N² (최대 225만)	N (최대 1500)
메모리	초과	통과
접근 방식	전체 저장	Top-N 유지

---

7. 시간 복잡도

• 전체 데이터: N²
• 힙 연산: O(logN)

→ 전체: O(N² log N)

(시간은 비슷하지만 메모리가 핵심 차이)

---

8. 중요한 포인트 정리

 1) 힙은 정렬 구조가 아니다

• heapq는 최소값만 빠르게 찾기 위한 구조
• 전체 정렬을 보장하지 않음

---

 2) "전체가 필요하지 않다"는 사고

이 문제의 핵심:

필요한 정보만 유지하는 것

---

 3) Top-K 문제 패턴

이 문제는:

Top-K (K=N) 문제

• 전체 저장 X
• K개만 유지 O