[ baekjoon ] 2075. N번째 큰 수

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 N번째 큰 수를 출력한다.

풀이

import sys 
import heapq

input = sys.stdin.readline

n = int(input())
arr = []

for _ in range(n):
  arr.append(list(map(int, input().split())))

# 마지막 행 heappush
q = []
for i in range(n):
  heapq.heappush(q, ((-1) * arr[n-1][i], (n - 1, i)))

idx = 0
while idx != n - 1:
  idx += 1
  now = heapq.heappop(q)[1] # 좌표 꺼내기
  if now[0] == 0:
    break
  heapq.heappush(q, ((-1) * arr[now[0] - 1][now[1]], (now[0] - 1, now[1])))
print((-1) * heapq.heappop(q)[0])

이 코드는 PyPy3로 채점해야 통과한다.
이 문제의 특징은 모든 수는 자신의 한 칸 위에 있는 수보다 크다 인데,
이것은 마지막 행에 가장 큰 수가 있다는 것을 알려준다.
즉, 마지막 행의 수들을 힙에 push한다. N번째 큰 이므로, 큰 수부터 pop해야하니 최대힙으로 구성한다.
이렇게 꺼낸 수의 한 칸 위에 있는 수를 다시 힙에 push한다.
이렇게 반복해서 N번째 큰 수를 찾으면 된다.
해당 좌표는 heap에 push할 때 두번째 인덱스에 튜플로 대입했다.

아이패드에 생각 정리하면서 푸니까 더 문제 접근이 잘 되는 것 같다.
앞으로 아이패드로 알고리즘 연습하는 습관 들여야겠당.