문제 정의
숫자로 이루어진 배열을 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열에서 가장 적은 수의 요소를 제거하여 남은 배열이 오름차순(증가 수열)이 되도록 만들어야 합니다.
접근 방법
기본적인 아이디어는 다음과 같습니다.
- 원본 배열을 보존하기 위해 배열의 복사본을 만듭니다.
- 배열을 순회하면서 현재 요소가 바로 다음 요소보다 큰 지점(감소 지점)을 찾아 해당 요소를 제거 대상으로 표시합니다.
- 마지막으로 표시된(
undefined) 요소들을 필터링하여 결과 배열을 반환합니다.
예제 코드
다음은 이를 구현한 코드입니다 −
const arr = [1, 100, 2, 3, 100, 4, 5];
const findIncreasingArray = (arr = []) => {
const copy = arr.slice();
for(let i = 0; i < copy.length; i++){
const el = arr[i];
const next = arr[i + 1];
if(el > next){
copy[i] = undefined;
};
};
return copy.filter(Boolean);
};
console.log(findIncreasingArray(arr));
실행 결과
[ 1, 2, 3, 4, 5 ]
코드 설명
위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.
arr.slice()를 사용해 원본 배열을 변경하지 않고 복사본을 생성합니다.- 반복문에서 각 요소와 그 다음 요소를 비교합니다.
- 현재 요소가 다음 요소보다 크면 증가 수열 조건에 어긋나므로 해당 위치를
undefined로 설정합니다. filter(Boolean)으로 falsy 값인undefined를 모두 걸러내면 증가 수열만 남게 됩니다.
입력 배열 [1, 100, 2, 3, 100, 4, 5]에서는 두 개의 100이 제거되어 [1, 2, 3, 4, 5]라는 완전한 증가 수열이 얻어집니다.
참고: 더 나은 접근 — 최장 증가 부분 수열(LIS)
위 방법은 인접한 두 요소만 비교하기 때문에 항상 최적의 결과를 보장하지는 않습니다. 예를 들어 [3, 4, 1, 5]처럼 중간의 1만 제거하면 되는 경우에도, 인접 비교 방식은 4를 제거해 [3, 1, 5]라는 잘못된 결과를 낼 수 있습니다.
정확히 최소 개수의 요소를 제거하려면 최장 증가 부분 수열(Longest Increasing Subsequence, LIS) 알고리즘을 사용하는 것이 좋습니다. 전체 배열 길이에서 LIS의 길이를 빼면 곧 제거해야 할 최소 요소 개수가 됩니다. LIS는 동적 계획법(DP) 또는 이진 탐색을 활용해 O(n log n) 시간에 효율적으로 구할 수 있습니다.