백준 12015번 "가장 긴 증가하는 부분 수열 2"

문제

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

풀이

11053번과 같은 문제지만 시간을 더 빡빡하게 보는거 같다.
문제해결법 자체는 같으니 참고 하시라.

11053번과 같이 DP를 활용하여 문제를 풀 경우 반복을 진행하며 배열의 뒤에 있는 수들의 순서를 재확인 할때 전부 확인하여 O(n^2)의 시간복잡도를 가지게 된다.
이 때 전부 확인하는 것이 아닌 이진탐색을 이용하여 확인하는 횟수를 줄인다면 O(nlogn)의 시간복잡도를 가지게 된다.

본문의 코드는 Pypy3 기준으로 통과하였다.

Python 코드

n = int(input()) 
a = list(map(int, input().split())) 
arr = [0] 

for x in a:
  start, end = 1, len(arr)-1
  while start < end:
    mid = (start+end)//2 
    if arr[mid] < x: 
      start = mid+1 
    elif arr[mid] > x: 
      end = mid 
    else: 
      start = end = mid 
  
  if arr[-1] < x: 
    arr.append(x) 
  else: 
    arr[start] = x 

print(len(arr)-1)