2075번 - N번째 큰 수(python3)

문제 링크 : https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

N*N 크기의 표에 수가 N*N개만큼 차 있는데, 모든 수는 바로 한 칸 위의 수보다 크다는 규칙을 가지고 있습니다. N=3일 때 예시로 다음과 같은 표를 만들 수 있습니다.

1	5	10
3	6	14
30	20	15

각 column마다 1 < 3 < 30, 5 < 6 < 20, 10 < 14 < 15를 만족합니다. 이러한 표가 주어졌을 때 N번째로 큰 수를 print하면 됩니다. 백준에서는 이 문제를 우선순위 큐로 분류했더군요.

import sys

n = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split())) #초기 N개 수

for _ in range(n-1): #N개씩 수가 들어올때마다
    tmp_lst = sorted(list(map(int, sys.stdin.readline().split())) + lst) #합치고 정렬
    lst = tmp_lst[n:] #가장 큰 N개만 빼서 저장

print(lst[0])

하지만 우선순위 큐를 쓰지 않고 풀었습니다..... N개의 숫자가 N번 입력되는데, 첫 번째 N개의 숫자만 받고 그 다음부터는 2N개의 수를 정렬하고 상위 N개만 빼는 식으로 풀었습니다. 야매로 푼 것 같지만... 어쨌든 풀었네요....

 

실은 문제를 처음 보고 작년 자료구조 수업 때 구현했던 loser tree를 사용하면 되겠다고 생각했습니다. 일단 N*N개 숫자를 모두 받고, transpose시킨 후, 큰 수가 이기는 loser tree competition을 N번 반복해서 나온 수가 N번째로 큰 수가 될 거라고 생각했습니다. 당시에 C로 구현해서 이번엔 python으로 구현해봤는데, 메모리 초과가 뜨면서 실패하고 말았네요..... 비록 문제는 못 풀었지만, 아까우니까 loser tree 관련 내용을 정리해서 글 하나 남기고 싶습니다..