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

문제 보러 가기!

NXN의 표에 수가 채워져있고, 모든 수는 자기 한 칸 위의 수보다 크다.

N번째 큰 수를 찾는 문제이다. (N은 1~1500이다.)

처음 - 메모리 초과

처음에는 extend를 이용해서 1차원 리스트로 N^2개의 값을 다 받았다. 이 문제에서 N번째로 '큰!!" 수를 찾아야 하므로 최대 우선순위 큐로 쓰려고 했다. 그래서 -1을 곱해서 넣어줬다. 그 후, 그 리스트를 우선순위 큐로 만들었다. heapq.heappop을 N번해서 N번째값을 출력했다. -1를 곱해서 넣어줬으니까, 출력할 때 -1을 곱한 후에 출력했다.
예제는 맞는데, 메모리 초과가 나왔다..
1500 X 1500 = 2250000 개를 리스트로 만들고 힙으로 만드는 게 너무 힘든가..

import sys, heapq

input = sys.stdin.readline

N = int(input())
arr = []
for _ in range(N):
    arr.extend(list(map(lambda k: int(k)*(-1), input().split())))

heapq.heapify(arr)

for _ in range(N-1):
    heapq.heappop(arr)

print(-1*heapq.heappop(arr))

나중 - 성공

우선순위 큐의 크기를 N으로 유지하는 식으로 문제를 풀었다. (우선순위 큐의 크기가 N일 때) 우선순위 큐에서 맨 앞 값이 그때까지 본 값 중에서 N번째 큰 수가 되는 것이다. 이때 사용한 것은 최소 우선순위 큐!! 맨 나중에 heapq.heappop한 값이 정답이 된다.

1. 값들을 한 줄씩 받아서, 하나 하나 보면서
   1-1. 우선순위 큐의 길이가 N보다 작으면, 우선순위 큐에 그 값을 넣는다.
   1-2. 우선순위 큐의 길이가 N과 같으면
   1. 1-2-1. 해당 값이 우선순위 큐에서 가장 작은 값보다 작거나 같으면 -> 그냥 넘어간다.
   2. 1-2-2. 해당 값이 우선순위 큐에서 가장 작은 값보다 크면 -> 우선순위 큐에서 가장 작은 값을 빼버리고(heapq.heappop), 해당 값을 큐에 넣는다.(heapq.heappush)
2. 모든 값을 그렇게 본 후에, heapq.heappop을 하면, N^2개의 수 중에 N번째로 큰 수가 나온다.

import sys, heapq

input = sys.stdin.readline

N = int(input())
arr = []
for _ in range(N):
    tmp = tuple(map(int,input().split()))
    for i in tmp:
        if len(arr) < N: # 큐의 길이가 N보다 작으면
            heapq.heappush(arr, i) # 큐에 값 넣기
        else: # 큐의 길이가 N과 같으면
            if arr[0] >= i: # 이번 값이 큐에 가장 작은 값보다 작거나 같으면
                pass # 넘어가기
            else: # 이번 값이 큐에 가장 작은 값보다 크면, 큐의 가장 작은 값 빼고 그 값으로 바꾸기
                heapq.heappop(arr)
                heapq.heappush(arr, i)
print(heapq.heappop(arr))