백준 2075 N번째 큰 수

 

import heapq, sys

input = sys.stdin.readline

heap = []

num = int(input())

for _ in range(num) : 
    array = list(map(int,input().split()))
    
    if heap :
        for a in array :
            if a > heap[0] :
                heapq.heappop(heap)
                heapq.heappush(heap, a)
    else :
        for a in array :
            heapq.heappush(heap, a)
    
    
print(heap[0])

 

힙을 이용해 해결했다.

 

모든 수를 다 넣고 해결하기에는 시간 복잡도가 매우 커진다.

 

파이썬은 최소 힙을 이용하기 때문에 힙의 크기를 N으로 제한하고, 0번째에 있는 수를 출력하게 되면 N번째 큰 수가 된다.