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

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

# N번째 큰 수
import sys
import heapq
input = sys.stdin.readline

N = int(input())
heap = []
for i in range(N):
    temp = list(map(int, input().split()))

    if i == 0:
        for x in temp:
            heapq.heappush(heap, x)
        continue

    for x in temp:
        if heap[0] < x:
            heapq.heappop(heap)
            heapq.heappush(heap, x)

print(heap[0])

 

힙

1. 한 줄씩 입력을 받고 첫 줄은 heapq에 push

2. 둘째 줄 부터는

    - heap[0]보다 큰 수만 push

    - 이때, heap의 크기를 N만큼 유지해주기 위해서 pop

3. heap[0] 출력

 

문제에서 눈여겨봐야 할 것은 바로 메모리 제한이다.

메모리 제한이 12MB이다.

또한, 'N번째 큰 수'이기에 최소 힙을 이용해서 힙의 크기를 N만큼 유지해줄 필요가 있다.