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

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

LIS알고리즘을 활용하면 쉽게 해결할 수 있는 문제다. 시간 복잡도는 O(NlogN)이다. LIS 알고리즘에 대해서는 아래 링크에서 자세히 확인할 수 있다. 이번 솔루션에서는 bisect를 활용한 것이 굉장히 독특하다.

LIS 알고리즘에 대하여

from bisect import bisect_left #이진탐색 코드, 같은 수일 경우 왼쪽 index를 돌려준다
import sys

input = sys.stdin.readline
A = list(map(int, input().split()))
lis = []

for i in A:
    k = bisect_left(lis, i) #자신이 들어갈 위치 k
    if len(lis) == k: #i가 가장 큰 숫자라면
        lis.append(i)
    else:
        lis[k] = i #자신보다 큰 수 중 최솟값과 대체
print(len(lis))