[백준 14003번] 가장 긴 증가하는 부분 수열 5 (bisect, python)

www.acmicpc.net/problem/14003

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

4번 문제와 똑같이 풀면 된다. 이번에는 q에 초기 숫자를 하나 넣어주는 대신 비어있거나 현재 원소가 q의 마지막 원소보다 크면 추가해주는 방식으로 했다. 

 

n의 범위만 달라지므로 초기값을 넣어줬었다면 이 부분만 주의하면 된다.

 

temp 배열을 출력하면 이렇게 나오고 

[(0, 10), (1, 20), (0, 10), (2, 30), (1, 20), (3, 50)]

 

ans 배열에 넣을 때 last_idx가 3, 2, 1, 0순으로 들어가는 흐름을 보면 된다.

 

import sys
from bisect import bisect_left

n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))

q=[]
temp=[]
for x in a:
    if not q or x>q[-1]:
        q.append(x)
        temp.append((len(q)-1,x))
    else:
        q[bisect_left(q,x)]=x
        temp.append((bisect_left(q,x),x))

ans=[]
last_idx=len(q)-1
for i in range(len(temp)-1,-1,-1):
    if temp[i][0]==last_idx:
        ans.append(temp[i][1])
        last_idx-=1
print(len(ans))
print(*reversed(ans))