PS Featured

[PS] BOJ 2075 / N번째 큰 수

Minjun Kim

02 Jan 2026 • 2 min read

Thumbnail: Photo by Zdeněk Macháček (Unsplash)

문제 링크: https://www.acmicpc.net/problem/2075

풀이

정렬로 풀기엔 적은 메모리

전체 $N^{2}$개의 수 중에서 $N$번째로 큰 수를 찾아야 합니다. 그런데, $1 \leq N \leq 1,500$이므로 우리가 비교해야 하는 수의 최대치는 2,250,000 개임을 알 수 있습니다. 단순히 수를 다 입력 받아 정렬하기엔 문제의 메모리 제한이 굉장히 작습니다. 어떻게 적은 메모리로 $N$번째로 큰 수를 찾을 수 있을까요?

우선순위 큐 활용하기

우선순위 큐를 활용하면 적은 메모리로도 $N$번째로 큰 수를 쉽게 찾을 수 있습니다.

길이 N의 우선순위 큐(최소 힙)를 생각해봅시다. 큐의 길이를 $N$으로 유지하면서 계속해서 큐에 가장 큰 $N$개의 수가 유지되도록 수를 넣다 보면, 이 우선순위 큐의 가장 앞 원소는 항상 $N$번째로 큰 수가 됩니다. 이를 활용하면 길이 $N$의 우선순위 큐만 사용해 $N^{2}$개의 수들을 모두 비교할 수 있습니다.

from heapq import heappush, heappop
pq = []
for _ in range(N):
    for num in map(int, input().split()):
        if len(pq) < N: # 큐에 N개보다 적은 수가 있다면 그냥 넣기
            heappush(pq, num)
        elif pq[0] < num: # 항상 큐의 길이가 N으로 유지되게끔 상위 N개의 수만 큐에 보존하기
            heappop(pq)
            heappush(pq, num)

백트래킹으로 길이가 N인 신기한 소수 만들기

전체 코드

from heapq import heappush, heappop
input = open(0).readline

N = int(input())
pq = []
for _ in range(N):
    for num in map(int, input().split()):
        if len(pq) < N:
            heappush(pq, num)
        elif pq[0] < num:
            heappop(pq)
            heappush(pq, num)

print(pq[0])

solution.py