[Python] 12738 - 가장 긴 증가하는 부분 수열 3 (골드2)

1. 문제 설명

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

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

 

[참고]

[Python] 11053 - 가장 긴 증가하는 부분 수열 (실버2)

[Python] 12015 - 가장 긴 증가하는 부분 수열 2 (골드2)

 

---

2. 아이디어

가장 긴 증가하는 부분 수열 2를 풀었다면 똑같은 로직으로 풀 수 있다.

한 가지 주의할 점은 처음에 0을 넣었던 지난 문제와 이번엔 음수가 포함되기 때문에

입력받은 값의 첫 번째 값을 lis 배열에 넣어버리고 2번 인덱스부터 탐색을 시켜야 정상적으로 굴러간다.

 

---

3. 코드

import sys

input = sys.stdin.readline

def solution():
    n = int(input())
    a = list(map(int, input().split()))
    lis = []
    lis.append(a[0])

    for current in a[1:]: # O(n)
        if lis[-1] < current:
            lis.append(current)
        else: # lis 값 갱신
            left = 0
            right = len(lis)

            while left < right: # O(log n) : 분할 탐색
                mid = (left + right) // 2

                if lis[mid] < current:
                    left = mid + 1
                else:
                    right = mid
            lis[right] = current
    print(len(lis))


solution()