Question
정수를 요소로 갖는 문자열을 입력받아 다음의 조건을 만족하는 LIS*의 길이를 리턴해야 합니다.
•
LIS: 배열의 연속되지 않는 부분 배열 중 모든 요소가 엄격하게 오름차순으로 정렬된 가장 긴 부분 배열(Longest Increasing Subsequence)
•
배열 [1, 2, 3]의 subseqeunce는 [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] 입니다.
•
엄격한 오름차순: 배열이 동일한 값을 가진 요소없이 오름차순으로 정렬되어 있는 경우를 말합니다.
입력
인자 1 : arr
•
number 타입을 요소로 갖는 배열
•
arr.length는 60,000 이하
•
arr[i]는 100,000 이하의 양의 정수
출력
•
number 타입을 리턴해야 합니다.
주의사항
•
LIS의 길이를 리턴해야 합니다.
•
LIS가 존재하지 않는 경우는 없습니다.
Test Case 1
let output = LIS([3, 2]);
console.log(output); // --> 1 (3 or 2)
Shell
복사
Test Case 2
output = LIS([3, 10, 2, 1, 20]);
console.log(output); // --> 3 (3, 10, 20)
Shell
복사
Solve
const LIS = function (arr) {
//TODO: 여기에 코드를 작성합니다.
let count = 0;
const stack = [];
for (let i = 0; i < arr.length; i++) {
if (stack.length === 0 || stack[stack.length - 1] < arr[i]) {
stack.push(arr[i]);
} else if (stack[stack.length - 1] > arr[i] && stack[stack.length - 2] < arr[i] || !stack[stack.length - 2]) {
stack.splice(-1, 1, arr[i]);
}
}
return stack.length;
};
JavaScript
복사
실행시간 : ms
dynamic programming with tabulation: O(N^2)
const LIS = function (arr) {
const N = arr.length;
// lis[i]는 i에서 끝나는 LIS의 길이를 저장
// 최소한 각 요소 하나로 LIS를 만들 수 있으므로 1로 초기화한다.
const lis = Array(N).fill(1);
for (let i = 1; i < N; i++) {
// i에서 끝나는 LIS의 길이
for (let j = 0; j < i; j++) {
// i 이전의 인덱스만 검사하면 된다.
// i는 1부터 시작하므로, 짧은 길이부터 검사한다. (bottom-up 방식)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
lis[i] = lis[j] + 1;
}
}
}
return Math.max(...lis);
};
JavaScript
복사
실행시간 : ms