---

문제 파악

문제는 N×N 개의 수가 주어질 때, N번째로 큰 수를 구하는 것이다.
N의 최대값은 1500이므로 전체 원소 수는 최대 2,250,000개다.

1. 처음 떠오르는 생각: 다 힙에 넣고 N번 pop?

가장 먼저 든 생각은 이거였다.

• 모든 값을 max-heap에 넣고
• N번 pop
• 마지막에 나온 값이 정답

하지만 이 방식은:

• N²개의 값을 전부 힙에 저장해야 하고
• push / pop 비용이 계속 발생해서 시간초과가 난다.

2. 사고 전환: 우리는 N번째 큰 수만 필요하다

N번째 큰 수의 정의를 다시 생각해보면:

• 지금까지 본 수 중 큰 값 N개만 유지하고
• 그 중 가장 작은 값이 바로 N번째 큰 수다.

그래서 전략은 다음과 같다.

• 크기 N짜리 min-heap 유지
• 힙에는 항상 “상위 N개 후보”만 존재
• 힙의 최솟값(heap[0]) = 현재 기준 N번째 큰 수

3. 시행착오: matrix에 전부 저장 → 시간 초과

처음에는 입력을 전부 matrix에 저장한 뒤 다시 순회했다.

• 입력 저장
• 다시 N×N 순회
• 힙 처리

이 방식은 파이썬에서 불필요한 메모리 + 반복 비용 때문에 시간 초과가 발생했다.

그래서 입력을 받는 즉시 처리하는 코드가 필요했다.

해답 코드

import sys
import heapq
input = sys.stdin.readline

N = int(input())
min_heap = []

for _ in range(N):
    min_heap.append(0)

for _ in range(N):
    row = map(int,input().split())
    for x in row:
        min_val = min_heap[0]
        if x > min_val:
    	    heapq.heapreplace(min_heap,x)

print(min_heap[0])

N번째로 큰 수가 필요하다면,
크기 N의 min-heap을 만들고 채워넣는 식으로 진행하자