[Python] 14003 - 가장 긴 증가하는 부분 수열 5 (플래티넘5)

1. 문제 설명

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

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

 

[참고]

[Python] 11053 - 가장 긴 증가하는 부분 수열 (실버2)

[Python] 12015 - 가장 긴 증가하는 부분 수열 2 (골드2)

[Python] 12738 - 가장 긴 증가하는 부분 수열 3 (골드2)

[Python] 12738 - 가장 긴 증가하는 부분 수열 4 (골드2)

이 문제를 위한 빌드업...

 

내 인생 첫 플래티넘 문제였다. 😊

이 악물고 통과..메모리가 압도적이다.

 

---

2. 아이디어

가슴이 웅장해지는 문제다.

DP는 시간초과로 틀리고, LIS는 순서가 뒤죽박죽이 되기 때문에 사용하지 못 한다.

그렇다면 방법은 LIS 알고리즘을 쓰되, 정상적인 배열은 따로 만들어줘야 한다는 얘기가 된다.

 

stack과 lis 이차원 배열을 만들고 2개의 인덱스는 각각 다음을 의미한다.

• lis[idx][0] : 증가 횟수
• lis[idx][1] : 입력받은 값 그냥 차례로 다 넣음.
• stack : 스택이라고 하기엔 좀 무리가 있지만, 기존 LIS 알고리즘에서 숫자가 뒤죽박죽 섞이던 배열 역할 담당.

중간 과정은 LIS Algorithm과 똑같이 수행한다.

이렇게 되면 stack의 길이를 체크함으로써 증가수열의 길이를 우선 출력할 수 있다.

그리고 또 한 가지 기능이 있는데, stack의 길이 - 1은 곧 lis[idx][0] (==증가 횟수)의 최대값을 의미한다.

즉, 역순으로 읽으면서 최대값과 일치하는 값을 만나면 -1씩 감소시키면서 매칭되는 수를 따로 저장한다.

이렇게 되면 가장 긴 부분 증가 수열이 역순으로 저장되므로 이를 다시 역순으로 출력하면 정답이 된다.

 

원래 그 당시에 stack의 stack을 구현해서 만들다가 실패했었는데 지금은 왠지 가능할 것 같아서

다시 풀어볼까 고민 중이다.

 

---

3. 코드

import sys

input = sys.stdin.readline

def lis_func(left, right, current, stack):
    while left < right:
        mid = (left + right) // 2

        if stack[mid] < current:
            left = mid + 1
        else:
            right = mid
    return right

def solution():
    n = int(input())
    a = list(map(int, input().split()))
    lis = [[0, 0] for _ in range(n)]
    stack, result = [], []
    
    lis[0][0], lis[0][1] = 0, a[0]
    stack.append(a[0])

    for idx in range(1, n):
        lis[idx][1] = a[idx]

        if stack[-1] < a[idx]:
            lis[idx][0] = len(stack)
            stack.append(a[idx])
        else:
            position = lis_func(0, len(stack)-1, a[idx], stack)
            lis[idx][0] = position
            stack[position] = a[idx]
    print(len(stack))

    max_length = len(stack) - 1
    for i in range(len(lis)-1, -1, -1):
        if lis[i][0] == max_length:
            result.append(lis[i][1])
            max_length -= 1
        if max_length == -1:
            break

    print(*result[::-1])


solution()