문제 이해
두 개의 배열 arr1과 arr2를 각각 첫 번째, 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.
이 함수의 목표는 두 배열 모두에 연속된 형태로 나타나는 부분 배열(subarray) 중 가장 긴 것의 길이를 반환하는 것입니다.
예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
입력
const arr1 = [1, 2, 3, 2, 1];
const arr2 = [3, 2, 1, 4, 7];
출력
const output = 3;
출력 설명
두 배열에서 가장 길게 반복되는 부분 배열은 [3, 2, 1]이며, 그 길이는 3입니다.
풀이 접근: 동적 계획법(DP)
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- dp[i][j]는 arr1의 i번째 요소와 arr2의 j번째 요소에서 끝나는 공통 부분 배열의 길이를 의미합니다.
- arr1[i]와 arr2[j]가 같다면, dp[i][j] = dp[i+1][j+1] + 1이 됩니다. 즉, 두 요소가 일치하면 이전까지의 공통 길이에 1을 더합니다.
- 일치하지 않으면 연속성이 끊기므로 dp[i][j] = 0으로 설정합니다.
모든 값을 계산한 뒤 dp 테이블에서 최댓값을 찾으면 정답을 얻을 수 있습니다.
구현 코드
다음은 위 로직을 구현한 코드입니다.
const arr1 = [1, 2, 3, 2, 1];
const arr2 = [3, 2, 1, 4, 7];
const maximumLength = (arr1 = [], arr2 = []) => {
const dp = new Array(arr1.length + 1)
.fill(0)
.map(() => new Array(arr2.length + 1).fill(0));
for (let i = arr1.length - 1; i >= 0; i--) {
for (let j = arr2.length - 1; j >= 0; j--) {
if (arr1[i] === arr2[j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
} else {
dp[i][j] = 0;
}
}
}
return dp.reduce((acc, items) => Math.max(acc, ...items), 0);
};
console.log(maximumLength(arr1, arr2));
실행 결과
3
코드 설명 및 복잡도 분석
위 코드는 배열의 뒤쪽부터 앞쪽으로 순회하면서 dp 테이블을 채워 나갑니다. 마지막에는 reduce 메서드를 사용해 2차원 배열 전체를 훑으며 최댓값을 추출합니다.
- 시간 복잡도: O(N × M) — N은 arr1의 길이, M은 arr2의 길이입니다.
- 공간 복잡도: O(N × M) — dp 테이블 저장에 필요한 공간입니다.
참고로, 슬라이딩 윈도우나 이진 탐색 기반의 접근법을 활용하면 공간 복잡도를 추가로 최적화할 수도 있습니다.