[백준14003번] 가장 긴 증가하는 부분 수열 5 / Python3

문제

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

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

입력

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

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

출력

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

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

나의 풀이

O(NlogN)으로 LIS를 구하기위해서는 lower_bound를 사용하는 알고리즘을 사용해야하는데 이렇게 구하면 1 3 4 2가 입력으로 주어지는 경우 최종으로 구해지는 LIS는 1 2 4가 됩니다. 따라서 이 문제에서는 배열을 앞에서부터 탐색하면서 해당 숫자가 들어갈 수 있는 인덱스에 대한 정보를 배열에 저장하고 이를 역추적하는 방법으로 풀이를 할 수 있습니다. 1 3 4 2를 예로들면 다음과 같습니다.

주어진 배열 : [1, 3, 4, 2]

각 원소가 LIS에 위치할 수 있는 인덱스 : [0, 1, 2, 1]

뒤에서부터 (LIS의 길이 - 1)부터 찾아 내려감 : 2(4) -> 1(3) -> 1(1)

코드

# 12738번 가장 긴 증가하는 부분 수열3


def lower_bound(start, end, num):
    while start < end:
        mid = (start + end) // 2

        if tmp[mid] < num:
            start = mid + 1
        else:
            end = mid
    return end


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

tmp = []
index = [[0, 0] for _ in range(n)]
for i in range(len(arr)):
    num = arr[i]
    index[i][1] = num

    if len(tmp) == 0:
        tmp.append(num)
        continue

    if tmp[-1] < num:
        index[i][0] = len(tmp)
        tmp.append(num)
    else:
        idx = lower_bound(0, len(tmp)-1, num)
        index[i][0] = idx
        tmp[idx] = num

answer = []
idx = len(tmp)-1
for i in range(len(index)-1, -1, -1):
    if idx == -1:
        break

    if idx == index[i][0]:
        answer.append(index[i][1])
        idx -= 1

print(len(tmp))
print(*answer[::-1])