[Baekjoon] 12015번 : 가장 긴 증가하는 부분 수열 2 (Python)

[Baekjoon] 12015번 : 가장 긴 증가하는 부분 수열 2 (Python)

 

목차

 

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

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

Python

 

방법 1 - 메모리 149432KB / 시간 2852ms / 코드 길이 364B

본 문제는 11053번 문제와 동일하나 시간복잡도를 줄여야한다.

https://aigong.tistory.com/385

[Baekjoon] 11053번 : 가장 긴 증가하는 부분 수열 (Python)

 

11053번은 DP를 통해 $O(N^2)$을 나타내지만 본 문제에서는 이분 탐색을 통한 시간복잡도를 $O(N\ log N)$이 가능하게 수정한다.

 

그러기 위해서는 전략이 필요한데 가장 긴 증가하는 부분 수열을 위해 추가적인 리스트를 할당한다.

다만 DP의 형식으로 이전의 값에 대한 점화식이 아닌 자신보다 큰 수 중 최솟값을 리스트에 넣는 방식으로 증가하는 부분 수열을 만들어낸다.

 

가령 예를 들어 [10, 20, 40, 30, 60, 25, 80]이 주어진다면 다음과 같은 순서로 부분 리스트가 만들어진다.

[10]
[10, 20]
[10, 20, 40]
[10, 20, 30]
[10, 20, 30, 60]
[10, 20, 25, 60]
[10, 20, 25, 60, 80]

 

물론 이 부분 리스트는 본래라면 [10, 20, 30, 60, 80]이 되어야 하지만 실제와는 다르게 구성된다.

그러나 이를 통해 가장 긴 길이의 리스트를 구할 수 있다.

 

n=int(input())
l=list(map(int, input().split()))
d = [l[0]]

def bs(target, start, end):
    while start <= end:
        mid = (start + end)//2
        if d[mid] < target:
            start = mid + 1
        else:
            end = mid -1
    return start

for i in l:
    if d[-1] < i:
        d.append(i)
    else:
        d[bs(i, 0, len(d)-1)] = i
print(len(d))

 

방법 2 - 메모리 151500KB / 시간 936ms / 코드 길이 199B

내장함수인 bisect를 통해서도 답을 구할 수 있다.

from bisect import bisect_left

n=int(input())
l=list(map(int, input().split()))
d = [0]

for i in l:
    if d[-1] < i:
        d.append(i)
    else:
        d[bisect_left(d, i)] = i

print(len(d)-1)