파이썬 백준 12738 가장 긴 증가하는 부분 수열 3

정글러 2021. 11. 17. 18:58

from bisect import bisect_left

n = int(input())

l = list(map(int, input().split()))

table = [l[0]]

for i in range(1, n):

if l[i] > table[-1]:

table.append(l[i])

else:

table[bisect_left(table, l[i])] = l[i]

print(len(table))

수열의 원소의 range는 +-10억으로 넓어졌지만, 수열의 길이는 12015와 마찬가지로 1,000,000이다

이분탐색을 이용한 대소비교에는 문제가 없으므로 12015와 같은 코드(https://uneducatedjungler.tistory.com/47)로도 시간 안에 제출할 수 있다.