[Python] 백준 2075번: N번째 큰 수(시간 복잡도 1등)

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

2075번: N번째 큰 수

import sys
input = sys.stdin.readline

N = int(input())

numbers = []
for _ in range(N):
    numbers.append(list(map(int, input().split())))

indices = [N-1]*N

for _ in range(N):
    maxNumber = numbers[indices[0]][0]
    maxIndex = 0
    for i in range(1, N):
        if maxNumber < numbers[indices[i]][i]:
            maxNumber = numbers[indices[i]][i]
            maxIndex = i

    indices[maxIndex] -= 1

indices[maxIndex] += 1
print(numbers[indices[maxIndex]][maxIndex])

마지막 라인을 가리키는 인덱스들을 indices에 담고, 거기서 max값을 찾아서 해당 인덱스를 1을 낮춰준다.

이것을 N-1번 반복하면 indices가 가리키는 값들의 max값은 우리가 찾는 값이 된다.