[Python/BOJ] 가장 긴 증가하는 부분 수열 4

https://www.acmicpc.net/problem/14002

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

풀이

Code

import sys, bisect
input = sys.stdin.readline

n = int(input())
array = list(map(int, input().split()))

# 1. 결과값 출력에 사용할 리스트 생성
result = [array[0]]
# 2. 갱신되는 인덱스의 위치와 값 설정을 위한 리스트 생성
perm = [(0, array[0])]
# 3. 리스트의 가장 큰 수와 비교
for i in range(1, n):
    # 3-1. 입력받은 수가 리스트의 가장 큰 수보다 클 경우
    if array[i] > result[-1] :
        result.append(array[i])
        # 인덱스의 위치와 값 저장
        perm.append((len(result)-1, array[i]))
    # 3-2. 입력받은 수가 리스트의 가장 큰 수보다 작을 경우
    else :
        # 값 초기화
        idx = bisect.bisect_left(result, array[i])
        result[idx] = array[i]
        # 인덱스의 위치와 값 저장
        perm.append((idx, array[i]))

ans = []
# 4. 생성된 리스트의 길이 정의
last_idx = len(result) - 1
for i in range(n-1, -1, -1) :
    # 4-1. 인덱스 순서에 맞게 출력 리스트에 삽입
    if perm[i][0] == last_idx :
        ans.append(perm[i][1])
        last_idx-=1

# 결과 출력
print(len(result))
print(*ans[::-1])