[백준] 12738 가장 긴 증가하는 부분 수열 3, python

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

 

 

LIS(가장 긴 증가하는 부분 수열), python

LIS(가장 긴 증가하는 부분 수열), python

 

 

 

LIS (Longest Increasing Subsequence)를 구하는 문제이다. n이 크기에 O(n²)로 풀면 시간초과가 나온다.

수열을 저장할 배열을 만든다. 수열에서 하나씩 탐색하며 배열이 비어있거나, 넣으려는 수열의 값이 배열의 마지막 인덱스보다 크면 배열에 집어넣는다. 만약 넣으려는 수가 배열의 마지막 인덱스보다 작다면 bisect_left를 통해 이진탐색으로 해당하는 인덱스에 값을 교체한다.

10 20 10 30 20 50의 경우를 보면

수열에서 넣으려는 값	LIS 배열	설명
10	[10]	배열이 비어있으므로 10 추가
20	[10,20]	수열에서 넣으려는값(20)이 배열의 마지막(10)보다 크므로 배열에 추가
10	[10,20]	넣으려는 값(10) 이 배열의 마지막값(20)보다 작으므로 LIS배열에서 넣으려는 값(10)의 인덱스 (0번째 인덱스) 를 찾아 교체(bisect_left 사용)
30	[10,20,30]	수열에서 넣으려는값(30)이 배열의 마지막(20)보다 크므로 배열에 추가
20	[10,20,30]	넣으려는 값(20) 이 배열의 마지막값(30)보다 작으므로 LIS배열에서 넣으려는 값(20)의 인덱스(1번째 인덱스)를 찾아 교체
50	[10,20,30,50]	수열에서 넣으려는값(50)이 배열의 마지막(30)보다 크므로 배열에 추가

 

이렇게 생성된 LIS 배열의 길이가 가장 긴 길이가 된다.

 

from bisect import bisect_left

n = int(input())
arr = list(map(int,input().split()))

lis = []

for i in range(n):
    x = arr[i]
    # 넣을 인덱스 찾기
    pos = bisect_left(lis,x)

    # 넣을 인덱스가 마지막이라면(LIS배열의 마지막값보다 크다면) 배열에 끝에 추가
    if pos>=len(lis):
        lis.append(x)
    
    # 아니면 교체
    else:
        lis[pos] = x

print(len(lis))