백준 2075 - N번째 큰 수 (파이썬)

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

풀이

문제의 핵심은 메모리 초과이다 N * N 크기의 행렬을 모두 메모리에 저장만 하더라도 메모리 초과가 일어나기 때문이다.

이를 효율적으로 처리하기 위해 우선순위 큐를 사용해 효율적으로 해결한다.

1. 행령을 읽어, 읽어온 각 숫자를 처리하며, 각각의 방식으로 힙을 유지한다.
2. 힙 크기가 N보다 작은 경우
   1. 그냥 heapq.heappush()로 추가
3. 힙 크기가 N과 같거나 큰 경우
   1. 만약 현재 힙의 최솟값 보다 큰 숫자가 들어오면, heapq.heappush()를 통해 추가한 후, heapq.heappop()으로 가장 작은 수를 제거하여 힙 크기를 N개로 유지한다.

시간 복잡도

1. 입력이 N*N이므로 총 N^2개의 숫자를 처리해야한다,
2. 각 숫자에 대해 heappush() 및 heappop()연산을 수행하며, 이는 O(logN)의 시간복잡도를 가진다,
3. 따라서 총 시간 복잡도는 O(N^2LogN)이다.

코드

# 백준 2075 - N번째 큰 수
# 분류 : 우선순위 큐
 
import heapq
 
N = int(input())
heap = []
 
for _ in range(N) :
    a = list(map(int, input().split()))
 
    for j in a :
        if len(heap) < N :
            heapq.heappush(heap, j)
        else :
            if heap[0] < j :
                heapq.heappush(heap, j)
                heapq.heappop(heap)
 
print(heap[0])