[백준] 12015번 : 가장 긴 증가하는 부분 수열 2

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

12015번: 가장 긴 증가하는 부분 수열 2

해당 문제는 아래의 문제의 시간복잡도를 개선 해야 하는 문제이다.

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

11053번: 가장 긴 증가하는 부분 수열

기존 11053 문제풀이는 시간복잡도가 최악의 경우 O(n^2)이다.

코드에서 dp테이블의 idx를 찾는 과정은 최악의 경우 O(n) 이다. 찾는 원소가 가장 제일 끝에 있을경우

N = int(input())
li = list(map(int,input().split()))
dp = [li[0]]

for i in range(1,N):
    if li[i] > dp[-1]:
        dp.append(li[i])
    else:
        j = len(dp)-1
        while j > 0:
            if dp[j-1] < li[i]:
                break
            j -= 1
        dp[j] = li[i]
print(len(dp))

파이썬에서 해당 원소를 이진탐색으로 O(logn)시간으로 찾을 수 있다. (bisect 활용)

따라서 해당 idx를 찾을때 bisect 를 활용하면 시간복잡도를 줄 일 수 있다.

 

from bisect import bisect_left
N = int(input())
arr = list(map(int,input().split()))

dp = [arr[0]]

for i in range(N):
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bisect_left(dp, arr[i])
        dp[idx] = arr[i]
            
print(len(dp))