LIS복원 - 14002번: 가장 긴 증가하는 부분 수열 4

• tail과 tail_idx 배열로 “길이 k+1인 증가 수열의 최솟값 꼬리”와 그 위치를 관리
• 새 값 x가 오면 bisect_left(tail, x)로 삽입 위치 pos를 찾아, 꼬리 추가 또는 교체
• prev_idx[i] = tail_idx[pos-1]로 각 원소가 연결될 이전 인덱스를 기록
• 최종 tail_idx[-1]에서 시작해 prev_idx를 거꾸로 따라가며 실제 LIS 수열을 복원!
  -> O(n log n) 시간에 LIS 길이와 수열을 모두 구할 수 있음

from bisect import bisect_left

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

# 실제 LIS 복원하는 유형 --------------------------


tail = []
tail_idx = [] # tail에 있는 원소가 nums에 있을 때의 idx 순서대로 저장
prev_idx = [-1] * n # tail에 있는 원소의 바로 앞(이전) 원소가 nums에 있을 때의 idx 저장 (인덱스도 idx, 저장되는 값도 idx)

for i, x in enumerate(nums):
    # tail에서 x가 들어갈 위치 pos를 이분탐색으로 구하기
    pos = bisect_left(tail, x)

    if pos == len(tail):
        # 지금까지 있던 tail의 원소들보다 더 큰 원소라면 맨 뒤에 추가
        tail.append(x)
        tail_idx.append(i)
    else:
        # 같은 길이에서 끝값을 더 작게 교체하기
        tail[pos] = x
        tail_idx[pos] = i

    # 이전 원소 연결하기, x가 들어간 위치 pos가 0보다 클 때(= x의 바로 왼쪽에 원소가 있을 때)
    if pos > 0:
        prev_idx[i] = tail_idx[pos - 1]


# lis 복원 ------------------------------
lis_length = len(tail)
lis = [0] * lis_length
cur = tail_idx[-1]

# lis의 뒤에서부터 거꾸로 prev_idx 따라 추적하기
for i in range(lis_length - 1, -1, -1):
    lis[i] = nums[cur]
    cur = prev_idx[cur]


print(len(lis))
print(*lis)

#for i in range(len(lis)):
#    print(lis[i], end=" ")