[백준] 가장 긴 증가하는 부분 수열 5 (Python)

백준 가장 긴 증가하는 부분 수열 5

LIS 알고리즘에 관하여

LIS 알고리즘을 활용하는 문제라고는 생각했지만, 길이뿐만 아니라 수열까지 구해야 문제라서 조금은 까다로웠다. 하지만 LIS 알고리즘에 트리의 부모를 찾는 알고리즘을 합쳐서 해결하면서 비교적 쉽게 해결할 수 있었다. LIS 테이블을 업데이트할 때마다. 앞에 있는 숫자를 트리의 부모로 지정한다. 업데이트할 때 0번째 인덱스라면 자신을 부모로 지정해야 한다. 마지막 인덱스에 업데이트가 되었지만 lis에 포함되지 않는 수를 제거하기 위해서, LIS 테이블의 마지막 요소는 가장 오래된 인덱스를 사용해야 한다.

1. LIS 테이블, 부모 트리를 저장할 dp 리스트, LIS 테이블에 저장된 값들의 인덱스를 저장할 LISIdx 리스트 3개를 선언한다.
2. LIS 테이블이 업데이트될 때마다, dp 리스트와 LISIdx 리스트도 같이 업데이트하되, 첫 번째 인덱스라면 dp 리스트는 업데이트하지 않는다.
3. 반복문이 끝나고 LISIdx 리스트에서 마지막 인덱스에 저장된 리스트 중에 첫 번째 인덱스(마지막 인덱스에 업데이트가 되었지만 lis에 포함되지 않는 경우 제거)부터 dp 리스트를 활용하여 부모 인덱스를 추적한다.

import sys
from collections import deque
from bisect import bisect_left

input = sys.stdin.readline
n = int(input().strip())
nList = list(map(int, input().split()))
lis = [nList[0]]
lisIdx = [[0]]
dp = [i for i in range(n)]

for i in range(1, n):
    if lis[-1] < nList[i]:
        dp[i] = lisIdx[-1][-1]
        lis.append(nList[i])
        lisIdx.append([i])
        
    else:
        k = bisect_left(lis, nList[i])
        if k != 0:
            dp[i] = lisIdx[k - 1][-1]
        lisIdx[k].append(i)
        lis[k] = nList[i]

idx = lisIdx[-1][0]
res = [nList[idx]]

while idx != dp[idx]:
    idx = dp[idx]
    res.append(nList[idx])

print(len(lis))
for i in range(len(lis) - 1, -1, -1):
    print(res[i], end = " ")