백준 2075 N번째 큰 수 -heap

2075번: N번째 큰 수 (acmicpc.net)

2075번: N번째 큰 수

이것도 우선순위 큐(heap)문제..

오늘 티어 바꾸려고 문제를 7개를 풀었더니 토할것같다.. 마지막문제.

 

import heapq
N = int(input())
heap = []
for i in range(N):
    a = list(map(int, input().split()))
    for j in a:
        heapq.heappush(heap, (-j, j))
for i in range(N):
    result = heapq.heappop(heap)[1]
print(result)

처음에 그냥 단순히 최소 힙 구하듯이 해서 다섯번째 수를 구하면되지않나? 했다.

결과는 나왔지만 메모리 초과가 떴음.

 

import heapq
N = int(input())
heap = []
for i in range(N):
    a = list(map(int, input().split()))
    if not heap:
        for j in a:
            heapq.heappush(heap, j)
    else:
        for num in a:
            if heap[0] < num:
                heapq.heappush(heap, num)
                heapq.heappop(heap)
print(heap[0])

그래서 찾아보니 담는 배열을 N크기로 유지시키고

그때마다 최솟값과 새로 들어온 값을 비교해서 더 작은 값은 pop하고 큰 값을 push하는 방법을 써야 메모리 초과가 뜨지 않는다.

새로 알게 된 사실: heap의 꼭대기 값은 무조건 최솟값이므로 heap[0]은 최솟값을 뜻한다.