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

 

문제

 

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

가장 긴 증가하는 부분 수열 2 / 골드 2 / 40분

사용한 알고리즘

- 이진 탐색

- 최장증가 수열 알고리즘(LIS)

 

한계

이 문제는 기본적인 dp를 이용해서는 시간초과가 발생하는 문제입니다.

시간제한이 1초이기 때문에 dp의 시간복잡도 - (O^2)

따라서 이진 탐색을 이용하여 문제를 풀어보겠습니다.

 

아이디어

기본 아이디어는 리스트의 값들을 Lower bound을 이용하여 해당 값보다 크거나 같은 인덱스를 반환해줍니다.

이 때 이 두 가지 경우가 나올것입니다

 

 

인덱스 < 리스트 길이

• 해당 인덱스의 값을 업데이트

    else:
        max_lists[idx] = number

인덱스 == 리스트 길이

• 해당 값은 리스트의 최대값보다 크므로 리스트의 길이를 늘림

if idx == len(max_lists):
        max_lists.append(number)

 

전체 코드

import sys
input =  sys.stdin.readline
n = int(input())
n_list = list(map(int,input().split()))

max_lists = []

# lower bound 
# target값 보다 같거나 큰 가장 작은 인덱스
def idx_check(arr,target):
    lo ,hi = 0, len(arr)-1
    while lo <= hi:
        m = (lo+hi)//2
        if arr[m] >= target:
            hi = m-1
        else:
            lo = m+1
    return lo

for number in n_list:
    idx = idx_check(max_lists,number)
    if idx == len(max_lists):
        max_lists.append(number)
    else:
        max_lists[idx] = number

print(len(max_lists))