[11053번] 가장 긴 증가하는 부분 수열 (python, bisect)

 

www.acmicpc.net/problem/11053

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

부분 수열의 길이만 구하는 문제고 실제 어떤 원소가 부분 수열을 이루고 있는지나 해당 원소의 인덱스를 구하는 문제가

아니라서 쉽게 구할 수 있다.

 

심지어 이 문제는 O(N*2)을 해도 풀리기 때문에 (1초= 10^9를 넘어가지 않으면 된다)

이중 반복문을 돌며 해당 원소 위치에서 가장 긴 부분 수열의 길이를 구하는 방식으로 구해도 되는데, 

 

가장 긴 증가하는 부분 수열의 풀이 방법 중 하나인 이분탐색, bisect를 공부하고 싶어서 해당 방법으로 풀어봤다

 

bisect_left는 해당원소가 배열에서 크기대로 몇 번째 인덱스에 해당하는 지 해당 인덱스를 반환해준다.

새로운 배열 q에 크기 순서대로 집어 넣으면서 해당 인덱스 위치에 더 작은 수가 들어갈 수 있으면 넣어준다.

 

이는 실제 q배열에 들어가는 원소를 궁금해하지 않고 길이만 구하는 문제이기 때문에 가능하다.

이분 탐색으로는 해당하는 위치를 찾을 때 bisect를 이용하지 않고 이분탐색으로 찾아주면 된다.

 

import sys
from bisect import bisect_left
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))

# 수열은 1<=n<=1000이다 0은 비교대상으로만 처음에 넣어주고
#마지막 길이 출력 때 1을 빼준다
q=[0]
for x in arr:
    if q[-1]<x:
        q.append(x)
    else:
        #bisect_left는 원소가 들어갈 위치를 반환해준다
        #길이를 구하는 문제에만 해당된다
        q[bisect_left(q,x)]=x
# print(q)
print(len(q)-1)