[ baekjoon ] 2075. N番目の大数

質問する

N×Nの表には数N 2個が充填されている.塗りつぶした数には、それぞれの数が自分の1つのグリッドの数より大きいという特徴があります.N=5の場合の例です.

このような表がある場合は、N番目の大きな数を検索するプログラムを作成します.表に記入されている数字はみな違います.

入力

第1行はN(1≦N≦1500)を与える.次のN行では、各行にN個の数が与えられる.表の数字は-10億以上、または10億未満の整数に等しい.

しゅつりょく

1行目は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])

このコードはPyPy 3で採点しなければ通過できません.
この問題の特徴は、すべての数が自分の格子の数より大きいことです.
これは私たちの最後の行に最大の数があることを教えてくれます.
つまり、最後の行の数をお尻に押します.N番目の大きいサイズなので、大きいサイズからポップにしますので、一番大きいお尻からなります.
こうして抽出した数の1つの格の数が再びお尻に押された.
これでN番目の大数を繰り返し探せばいいのです.
heapにプッシュすると、座標は2番目のインデックスに変換されます.
iPadで考えを整理して問題を解くと問題に近づきやすい感じがします.
これからはiPadでアルゴリズムを練習する習慣を身につけましょう.