[python 백준 2075] N번째 큰수

📜 접근 방법

처음에는 heap에 내림차순으로 넣고 n만큼 빼면 n번째 큰수가 나오는 것을 생각하여 코드를 짰다.

하지만 메모리 오류 발생했다.

 

heap안에 원소의 갯수를 제한시켜서 갯수가 n개 이상이면

현재 넣어야할 원소와 heap안에 있는 제일 작은 수를 비교한다.

현재 넣을 원소가 크다면 heap[0](가장 작은 수)에 있는 수를 pop하고 집어넣는다. 아닐경우 넘어간다.

 

❌ 실패 코드

메모리 오류

from heapq import heappush, heappop
import sys

input = sys.stdin.readline

n = int(input())
heap = []
for i in range(n):
    tmp = list(map(int, input().split()))
    for num in tmp:
        heappush(heap, -num)

for i in range(n):
    res = -heappop(heap)
print(res)

✅ 정답 코드

from heapq import heappush, heappop
import sys

input = sys.stdin.readline

n = int(input())
heap = []
for i in range(n):
    tmp = list(map(int, input().split()))
    for num in tmp:
        # heap의 용량이 n이 넘어가면 pop하여 제일 작은 수부터 제거해줌
        if len(heap) < n:
            heappush(heap, num)
        else:
            if heap[0] < num:
                heappop(heap)
                heappush(heap, num)

# n개 남은 힙에 첫번째가 n번째로 큰수이기 때문에 heap[0]
print(heap[0])

 

💡알게 된점

메모리에 대해서도 좀 생각을 해보는 시간을 가졌다.