[백준] 12015번 파이썬 - 가장 긴 증가하는 부분 수열 2

문제

 

첫 코드

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

answer = 0
dp = [1] * (n)

for i in range(0,n):
    dp[i] = 1
    tmp = 0
    for j in range(i+1,n-i):
        if lst[i] < lst[j] and lst[j] > tmp:
            tmp = lst[j]
            dp[i] += 1

print(max(dp))

 

다이나믹 프로그래밍을 사용하여 풀었고(LIS 알고리즘), 시간초과가 났다.

문제 제목만 보고 입력 조건을 확인하지 않았다..

 

위 코드의 시간복잡도를 계산해보니

첫 for문에서 n, 두번째 for문에서 i부터 n까지 돈다고 해도

결국 시간복잡도는 O(N^2)가 된다.

 

따라서 시간복잡도를 줄일 수 있는 다른 풀이법을 생각해내야 했다.

 

 

정답 코드

이분탐색을 사용하여 문제를 해결하였다. (시간복잡도 O(nlogn))

import sys
input = sys.stdin.readline

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

ans = [lst[0]]

def binarySearch(n):
    start = 0
    end = len(ans) - 1

    while start<=end:
        mid = (start + end) // 2

        if(lst[mid] == n):
            return mid
        elif lst[mid] < n:
            start = mid+1
        else:
            end = mid-1
    return start

for i in range(n):
    if lst[i] > ans[-1]:
        ans.append(lst[i])
    else:
        idx = binarySearch(lst[i])
        ans[idx] = lst[i]
    
print(len(ans))

 

너무 어려웠다.

이분탐색을 쓰겠다는 생각도 나지 않았고

이분탐색을 쓴지도 오래되어서 

결국 답지를 참고하여 작성했다.

여러번 보고 분석해서 다음에 내 힘으로 다시 풀어야지..