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

백준 12015

https://st-lab.tistory.com/285

새로 들어오는 값이 현재 리스트의 마지막 값보다 크면 리스트 마지막에 추가해주면 된다.
더 작은 값이 들어오게 되면 현재 가지고 있는 리스트에서 이 값이 어디에 들어가야 할 지 정해줘야한다.
이 과정을 이분 탐색으로 구현하고, 들어갈 위치를 찾았다면 그 위치의 값을 더 작은 현재 들어온 값으로 바꿔준다. 길이만 구하면 되므로 이런식으로 중간의 값을 바꿔서 풀면 된다.

def bi_search(arr, x): # or import bisect
    start, end = 0, len(arr)
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] < x:
            start = mid + 1
        else:
            end = mid - 1
    return start

N = int(input())
A = list(map(int, input().split()))

lis = [0]
for i in range(N):
    if lis[-1] < A[i]: # 들어온 값이 더 크다면 
        lis.append(A[i]) # 바로 추가
    elif lis[-1] > A[i]: # 작다면
        idx = bi_search(lis, A[i]) # bisect.bisect_left(lis, A[i])
        lis[idx] = A[i] # 처음으로 더 리스트에서 더 큰 값이 나타나는 인덱스 찾은 후 교체

print(len(lis)-1)