[Python][백준 12015][이분 탐색] 가장 긴 증가하는 부분 수열 2 - 컴도리돌이

반응형

 

---

풀이 과정

해당 문제는 bisect 라이브러리를 사용해서 해결하였다.

bisect에 대해서는 아래 링크를 참조하면 좋다.

 

[Python] bisect - 컴도리돌이

 

1. 입력받은 배열의 0번째 인덱스 값부터 순차적으로 반복문을 시행한다.

 

2. arr가 비어있으면 x 값을 arr에 insert 한다.

 

3. 현재 x 값이 arr의 마지막 인덱스 값보다 크면 insert 시킨다.

 

4. 마지막 인덱스 값보다 크지 않으면 bisect_left 함수를 이용해서 

x값보다 같거나 작은 값의 인덱스에 x를 저장한다.

 

5. arr의 크기를 출력한다.

---

풀이 코드

from bisect import bisect_left
n,*X = map(int,open(0).read().split())
arr = []
for x in X :
  if not arr : arr.append(x) ; continue
  if arr[-1] < x : arr.append(x)
  else : arr[bisect_left(arr,x) ] = x
print(len(arr))