|
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))
|
11053과 같은 문제이지만, 에 비해 range가 커졌다.
즉, 11053의 코드(https://uneducatedjungler.tistory.com/45)처럼 원소 하나하나에 대해 자기보다 이전 index의 원소를 for문으로 뒤져가며 자기가 들어갈 위치를 찾기엔 시간이 부족하다.
단순탐색으론 안되니 이분탐색을 써야 할텐데, 이분탐색은 정렬된 리스트에 대해서만 쓸 수 있으므로 각 원소의 order만 세주는 리스트로는 부족하다.
직접 각 원소를 담는 부분수열 리스트를 만들어서 그 안에서 (증가하는 부분수열이니 sort되어있음을 이용하여) 이분탐색으로 빠르게 자기 위치를 찾는다.
이 기능을 해주는 bisect를 쓰면 편하게 구현할 수 있다. (오히려 더 짧아진 것 같다.)
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 14002 가장 긴 증가하는 부분 수열 4 (0) | 2021.11.17 |
|---|---|
| 파이썬 백준 12738 가장 긴 증가하는 부분 수열 3 (0) | 2021.11.17 |
| 파이썬 백준 11722 가장 긴 감소하는 부분 수열 (0) | 2021.11.17 |
| 파이썬 백준 11053 가장 긴 증가하는 부분 수열 (0) | 2021.11.16 |
| 파이썬 백준 11053 공유기 설치 (0) | 2021.11.16 |