[12738] 가장 긴 증가하는 부분 수열 3

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

다른 가장 긴 증가하는 부분 수열과 비슷한 문제이다. N (1 ≤ N ≤ 1,000,000)에 3초이기 때문에 이분탐색을 사용하거나, 이중 포문을 사용하거나 둘중 아무거나 사용해도 시간에는 문제가 없을 것이다.

이번에는 이분탐색을 이용했다.

LIS 와 같이 길이에 따라 최대값을 lis 배열에 넣어두고, 해당 값 보다 큰 경우 +1 을 시킨다. 아닌 경우에는 이분탐색을 통해서 들어갈 수 있는 길이에 업데이트 시킨다.

풀이

import sys

def bs(left, right, i):
    while(left <= right):
        mid = (left+right)//2
        if lis[mid] < nums[i]:
            left = mid + 1
        else:
            right = mid-1
    return left

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    nums = list(map(int, sys.stdin.readline().split()))
    cnt = 1
    lis = list( 0 for _ in range(N))
    lis[0] = nums[0]

    for i in range(N):
        if lis[cnt-1] < nums[i]:
            lis[cnt] = nums[i]
            cnt += 1
        else:
            left = 0
            right = cnt
            ind = bs(left, right, i)
            lis[ind] = nums[i]

    print(cnt)