문제

Baekjoon2075: N번째 큰 수

설명: $N^2$의 행렬이 주어질 때 $N$번째 큰수를 구하여라. 단 행렬은 한 칸 위에 있는 수보다 크다.

풀이

접근 1

가장 쉽게 풀 수 있는 방법은 행렬을 모두 배열에 넣고 정렬한 뒤 $N$번째로 큰 수를 찾거나
우선순위 큐(max heap)에 다 넣고 $N$번 값을 꺼내면 된다.
- 실제로 이 방법으로 풀리는 것 같다.

접근 2

하지만 주어진 문제가 열 기준 우선순위 큐의 형태를 띄고 있고, 메모리 제한이 굉장히 작기 때문에 뭔가 행렬을 깨뜨리지 않고 풀고 싶었다.
각 열마다 포인터를 둔다. 시작점은 가장 마지막 행이다.
이 $N$개의 포인터가 가르키고 있는 수 중 가장 큰 값을 찾고, 그 포인터를 $1$ 감소시킨다.
- 즉, 자신의 열 중에 자기보다 작은 값을 선택하도록
이 방법을 $N$번 반복한 뒤, 가장 큰 값이 $N$번째 큰 값이다.
시간복잡도는
- 가장 큰 값을 찾는 행위 $N$, 이 방법을 $N$번 반복하기에 $O(N^2)$이다.

오늘의 회고

요즘 바쁘다는 핑계로 챌린저 문제를 풀지 못해 다른 풀이를 올린다...
나태해진 것 같지만 나중에 언젠가 꼭 풀어서 풀이를 남겨놓겠다..!

Code

# Baekjoon02075.py
import sys
input = sys.stdin.readline

n = int(input())
mat = [list(map(int, input().split())) for _ in range(n)]

indexes = [n - 1] * n

def get_biggest_index():
    s_col = 0 # biggest_column
    for i in range(n):
        if indexes[i] >= n:
            continue

        if s_col >= 0:
            if mat[indexes[s_col]][s_col] < mat[indexes[i]][i]:
                s_col = i
        elif s_col < 0:
            s_col = i

    return s_col

for _ in range(n - 1):
    indexes[get_biggest_index()] -= 1    

ans = get_biggest_index()
print(mat[indexes[ans]][ans])