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

본문 링크

from bisect import bisect_left
import sys
input=sys.stdin.readline

N=int(input())
L=list(map(int,input().split()))
dp=[]
check=[]

for i in L:
    if not dp:
        dp.append(i)
    if dp[-1]<i:
        dp.append(i)
        check.append((len(dp) - 1, i))
    else:
        index=bisect_left(dp,i)
        check.append( (index,i))
        dp[index]=i

answer=[]
last_index=len(dp)-1
for i in range(len(check)-1,-1,-1):
    if check[i][0]==last_index:
        answer.append(check[i][1])
        last_index-=1
print(len(answer))
print(*answer[::-1])

📌 어떻게 탐색할 것인가?

이 문제에서는 가장 긴 증가하는 부분수열의 길이와 그때의 배열을 구하는 문제이다.

이전 시리즈 문제에서 배열을 구할때에는 $O(NlogN)$ 으로 가장 긴 증가하는 부분수열이
길이만 구할수 있을 뿐 배열을 구할순 없기 때문에 $O(N^2)$ 의 알고리즘으로 배열을 구하였다.

하지만 문제에서 $N$ 의 범위는 $N (1 ≤ N ≤ 1,000,000)$ 이다.

즉 $O(Nlog N)$ 의 알고리즘으로 가장 긴 증가하는 부분수열의 길이와 그때의 배열을 같이 구해야한다.

이전에 앞서 이분탐색과 bisect 알고리즘으로 O(Nlog N) 을 통한 가장 긴 증가하는 부분수열의 길이는 구하였기 때문에
배열을 구하는 방법에 대해서 알아보고자 한다.

📌 어떻게 배열을 구할 것인가?

먼저 check 배열을 만들어 준다.
이후 매번 $dp$ 배열에 값이 추가될때마다 ( len(dp)-1 , 값) 과 같은 튜플의 형식으로
check 배열에 원소를 추가해준다. bisect 라이브러리로 원소를 추가할때는 check.append((index,i)) 와 같이 추가해준다.

이후 check 배열을 보면 check[0][[0] 에는 $dp$ 배열에 원소를 추가한 시간 , check[0][1] 는 그때의 값을 나타낸다.

이때 우리는 역추적을 하여서 뒤에서부터 값이 처음으로 감소하는 지점을 매번 찾아준다.
(3,50) , (2,30) , (1,20) , (0,10) 이 바로 그것이다.

3 번째로 큰값 , 2 번째로 큰값 ,1 번째로 큰값 , 0 번째로 큰값을 구하면
50 30 20 10 이되고 역순으로 10 20 30 50 이다.

따라서 check 배열을 만들어 주고 $dp$ 에 저장되는 시점과 그 값을 저장해주면
반복문 한번으로 최장 길이 배열을 구할 수 있다.