[백준] 14002. 가장 긴 증가하는 부분 수열4 풀이 / Python, JavaScript

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

 

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

부분 수열 1 문제와 동일한 문제이지만 여기서는 길이 뿐만 아니라 구성되는 수열을 출력해야 합니다.

가장 긴 증가하는 부분 수열 1문제에 대한 풀이는 아래에 남겨놓았습니다.

[백준] 11053. 가장 긴 증가하는 부분 수열 풀이 / Python, JavaScript

기본적인 문제해결 아이디어는 다음과 같습니다. 

현재 수가 V수일 때, 수열은 V보다 작은 정수들 중에서 가장 긴 수열에 V를 추가한 수열이다. 

예시로 주어진 입력을 봅시다.

 

10 20 10 30 20 50

기본적으로 수열의 값을 하나씩 순회합니다. 그리고 매 순회의 결과를 담은 것을 테이블이라고 하겠습니다. 

 

1. 현재 수는 10이고 10을 제외하고 지금까지 순회한 값(없음)들을 고려했을 때 10보다 작은 정수는 없습니다. 10테이블에는 []에 원소 10을 추가한 [10]이 저장됩니다. (이는 현재 수가 10일 때, 수열이 [10]으로 구성된다는 것을 의미합니다) 

2. 현재 수는 20이고 20을 제외하고 지금까지 순회한 값(10)들을 고려했을 때 20보다 작은 정수가 있습니다. 순회한 값들에 해당하는 테이블 중에서 20보다 작으면서 가장 길이가 긴 수열을 가지고 있는 테이블은 10테이블입니다. 따라서 20테이블에는 [10]에 원소 20을 추가한 [10, 20]이 저장됩니다. 

3. 현재 수는 10이고 10을 제외하고 지금까지 순회한 값(10, 20)들을 고려했을 때 10보다 작은 정수는 없습니다. 10테이블에는 []에 원소 10을 추가한 [10]이 저장됩니다. 

4. 현재 수는 30이고 30을 제외하고 지금까지 순회한 값(10, 20, 10)들을 고려했을 때 30보다 작은 정수가 있습니다. 순회한 값들에 해당하는 테이블 중에서 30보다 작으면서 가장 길이가 긴 수열을 가지고 있는 테이블은 20테이블입니다. 따라서 30테이블에는 [10, 20]에 원소 30을 추가한 [10, 20, 30]이 저장됩니다. 

5. 현재 수는 20이고 20을 제외하고 지금까지 순회한 값(10, 20, 10, 30)들을 고려했을 때 20보다 작은 정수가 있습니다. 순회한 값들에 해당하는 테이블 중에서 20보다 작으면서 가장 길이가 긴 수열을 가지고 있는 테이블은 10테이블입니다. 따라서 20테이블에는 [10]에 원소 20을 추가한 [10, 20]이 저장됩니다. 

6. 현재 수는 50이고 50을 제외하고 지금까지 순회한 값(10, 20, 10, 30, 20)들을 고려했을 때 50보다 작은 정수가 있습니다. 순회한 값들에 해당하는 테이블 중에서 50보다 작으면서 가장 길이가 긴 수열을 가지고 있는 테이블은 30테이블입니다. 따라서 50테이블에는 [10, 20, 30]에 원소 50을 추가한 [10, 20, 30, 50]이 저장됩니다. 

7. 모든 수를 순회했고 테이블에서 가장 길이가 긴 수열은 50테이블의 [10, 20, 30, 50]이며 길이는 4입니다.

 

작성 코드 (.py)

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
table = [[] for _ in range(max(arr) + 1)]
for v in arr:
    table[v] = max(table[:v], key=lambda x: len(x)) + [v]
result = max(table, key=lambda x: len(x))
print(len(result))
print(*result)

작성 코드 (.js)

function solution(n, arr) {
  const table = Array(Math.max(...arr) + 1).fill([]);
  arr.forEach((v) => {
    const targetScope = table.slice(0, v);
    const targetLens = targetScope.map((v) => v.length);
    table[v] = table[targetLens.indexOf(Math.max(...targetLens))].concat(v);
  });
  const resultLens = table.map((v) => v.length);
  const resultIdx = resultLens.indexOf(Math.max(...resultLens));
  return [table[resultIdx].length, table[resultIdx]];
}
solution(6, [10, 20, 10, 30, 20, 50]);