[BOJ] 백준 2075 N번째 큰 수 Python

2075번: N번째 큰 수

문제풀이
첫번째 시도) N번째 큰 수를 단순히 최대힙을 만들어 구하려고 했다. 1 ≤ N ≤ 1500 라는 N의 범위값과 12MB라는 메모리 공간 제한 때문에 메모리 제한이 나왔다.

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline


n = int(input())
arr = []
tmp_arr = []
for _ in range(n):
    tmp_arr = list(map(int, input().split()))
    for num in tmp_arr:
        heappush(arr, -num)
for _ in range(n):
	k = heappop(arr)
print(k)

✅두번째 시도)
이에 힙의 크기를 항상 N으로 만들어주어서 최소힙의 첫번째 원소보다 큰 원소가 들어오면 교체를 해주면 될거라는 생각이 들었다.
💡그렇게 되면 힙의 크기가 N일때 힙의 첫번째 원소는 N번째 큰 수가 된다.
왜냐하면 힙은 최소힙으로 첫번째 원소 이후에 첫번째 원소보다 N-1개의 큰 수들이 필연적으로 존재하기 때문이다.

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline

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

🧠알고리즘
1. 힙이 비어있을 땐 배열을 무조건 힙에 push한다.
2. 이렇게 될 경우 첫시행이 끝난 후 힙에는 반드시 N개의 원소가 차있는데 이 때 첫번째 원소와 새로 들어오는 입력에 대해서 비교를 진행한후 힙을 갱신한다.
3. 힙의 첫번째 원소(N번째 큰 수)를 출력한다.