2022.02.19 [백준] (python 파이썬) N번째 큰 수

 

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

2075번: N번째 큰 수

 

---

풀이

이 문제는 heap을 사용해서 해결했다.

문제에서 n*n의 표가 주어진다. 그리고 n번째 큰 수를 출력해야 한다.

모든 수를 heap에 저장 후, n번째 큰 수를 찾으면 메모리 초과가 발생한다.

그래서 첫 줄을 heap에 추가한다. 그러면 heap에 n개의 수가 들어가고 루트노드에는 최소값이 오게 된다.

그래서 다음 줄부터 값을 최소힙과 비교해서 최소힙보다 크면 pop후 큰 값을 push해준다.

모든 비교가 끝나면 힙에는 표에서 가장 큰 수 5개가 들어가게 되고 루트노드에는 n번째 큰 수가 위치하게 된다.

 

import heapq
import sys
 
input=sys.stdin.readline
 
n=int(input())
arr=[]
heap=[]
x=list(map(int, input().split()))
for i in range(n):
    heapq.heappush(heap,x[i])
for _ in range(n-1):
    a=list(map(int,input().split()))
    for i in range(n):
        if heap[0]<a[i]:
            heapq.heappop(heap)
            heapq.heappush(heap, a[i])
 
print(heapq.heappop(heap))