[백준 14002번] 가장 긴 증가하는 부분 수열 4 (python, bisect, 어려움)

www.acmicpc.net/problem/14002

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

1,2,3 까지는 쉬웠는데 4부터 난이도 급상승 ㅠ O(n^2)으로 푼 사람이 많은데 n이 커진 문제인 경우 못풀걸 알아서

더 줄여서 풀고 싶었다 

 

혼자서 시도해보다가 다른 사람 풀이 참고해서 풀었다. 아직 알고리즘 머리가 부족하군.. 

 

이전 문제들에서 이전보다 더 작은 수가 등장했을 때 위치를 갱신하는 것은 익숙할 것이다.

여기서는 실제 요소를 구해줘야하므로 해당 위치값과 실제 요소 값을 저장하는 배열 t를 하나 더 추가한다.

 

1. 위치에 들어가는 요소를 갱신하며 실제 배열의 길이를 구한다.

2. 뒤에서 부터 되돌아가며 각 위치에 원래 요소 값을 넣어준다.

 

구한 배열의 길이가 3이면 2에 해당하는 요소를 넣고 1에 해당하는 요소를 넣고 0에 해당하는 요소를 넣고 뒤집는다.

t 배열의 경우 앞에 있는 것이 원래 요소이고 뒤에 있는게 기존 값을 덮어버린 가짜 값(?)이다. 

 

설명이 어려운데 밑의 코드를 보며 예제 숫자를 넣어보면 이해가 될 것이다. 참고로 2시간 이상은 푼 것같다

이문제 ㅠㅠ.... 

 

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

q=[arr[0]]
t=[] # (들어갈 위치, 값)의 쌍을 넣는 배열
# 여기는 이전 문제들과 비슷하다.
#  다만 t라는 새로운 배열에 갱신되는 배열 요소의 위치, 요소 값에 대한 정보도 추가하는게 다르다
for x in arr:
    if q[-1]<x:
        q.append(x)
        t.append((len(q)-1,x))
    else:
        idx=bisect_left(q,x)
        q[idx]=x
        t.append((idx,x))
        
# 최종 배열의 길이를 구했으면 마지막 위치부터 가장 큰 요소를 넣는다 (실제 요소)       
last_idx=len(q)-1

# 덮어씌워진 요소가 아니라 기존 요소를 넣어준다 
ans=[]
for i in range(n-1,-1,-1):
    if t[i][0]==last_idx:
        ans.append(t[i][1])
        last_idx-=1

# print(q)
# print(t)
print(len(q))
# *을 붙이면 자동으로 리스트 요소를 공백으로 구분해 반환해준다
print(*reversed(ans))