2075 - N번째 큰 수
📌 문제
N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.
이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.
📋 코드
import heapq
N = int(input())
q = []
for i in range(N):
arr = list(map(int, input().split()))
for num in arr:
heapq.heappush(q, num)
while len(q) > N:
heapq.heappop(q)
print(heapq.heappop(q))💡 한마디
처음 시도할 때에는 최대 힙으로 접근했다. 숫자에 마이너스(-)를 붙여 힙에 모두 넣은 뒤 N번째 뺀 값이 정답이지 않을까 생각했다. 물론 답은 맞게 떴지만 2차원 배열을 전부 입력받고, 모든 수를 힙에 넣어 진행한 탓에 메모리 초과가 떴다.
다른 사람 풀이를 참고하여 푼 결과 코드는 위와 같다. 2차원 배열 한 행씩 힙에 넣고, 힙에 들어있는 수의 개수가 N이 될때까지 다시 빼줬다. 그 결과 힙에는 매 순간마다 가장 큰 N개의 수가 남아있게 된다.
