[정렬 문제] 백준 2075번: N번째 큰 수 / 골드 5

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

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

www.acmicpc.net

import heapq
n = int(input())

table = [[0]*n for x in range(n)]
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(n):
        table[j][i] = row[j]

q = []
for i in range(n):
    heapq.heappush(q, (-table[i].pop(), i))

for i in range(n):
    num, idx = heapq.heappop(q)
    if i == n-1:
        print(-num)
        break
    next = table[idx].pop()
    heapq.heappush(q, (-next, idx))

최대힙으로 풀이가 가능하다.

데이터의 행, 열을 뒤집어 테이블에 저장해주고

끝에서부터 하나씩 빼서 q에 넣어주고,

최대힙으로 최댓값을 계속 pop해준다.

빠진 최댓값의 idx를 받아와 그 테이블에서 pop해서 q에 넣어준다.

이를 n번 반복하면 된다.