[LeetCode] 718. Maximum Length of Repeated Subarray

문제 출처: https://leetcode.com/problems/maximum-length-of-repeated-subarray/

Maximum Length of Repeated Subarray - LeetCode

 

문제

두 정수 배열 nums1과 nums2가 주어지면, 두 배열에서 공통적으로 나타나는 서브배열의 최대 길이 를 반환하라.

 

예제

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

Explanation: The repeated subarray with maximum length is [3,2,1].

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5

 

풀이

두 배열의 공통의 서브배열을 찾기 위해 아래와 같은 방식으로 두 배열을 비교해 갈 수 있다.

nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]

1) 첫 번째 비교
nums1 = [1, 2, 3, 2, 1]
nums2 = [3, 2, 1, 4, 7]
-------------------------
        [F, T, F, F, F]

2) 두 번째 비교
nums1 = [1, 2, 3, 2, 1]
nums2 =    [3, 2, 1, 4, 7]
-------------------------
           [F, F, F, F]

3) 세 번째 비교
nums1 = [1, 2, 3, 2, 1]
nums2 =       [3, 2, 1, 4, 7]
-------------------------
              [T, T, T]

...

5) 다섯 번째 비교
nums1 = [1, 2, 3, 2, 1]
nums2 =             [3, 2, 1, 4, 7]
-------------------------
                    [F]

위 예제는 nums1을 기준으로 nums2를 이동시키며 공통의 부분을 찾았다. 반대로 nums2를 기준으로 nums1을 이동시키는 것까지 고려해야 한다.

 

이러한 방식을 코드로 만들어보자. 우선, 전체적인 구조를 만들면 아래와 같은 모습이 될 것이다.

var findLength= = function(nums1, nums2) {
    let ans = 0;

    if (nums1.length < nums2.length) { [nums1, nums2] = [nums2, nums1]; }

    // 비교 시작 지점 설정을 위한 반복
    for (let i = 0; i < nums1.length; i++) {
        const tmp1 = compareTo(nums1, nums2, i);    // nums1[i]부터 nums2와 비교한 결과
        const tmp2 = compareTo(nums2, nums1, i);    // nums2[i]부터 nums1과 비교한 결과
        ans = Math.max(ans, tmp1, tmp2);
    }

    return ans;
};

위 코드에서 compareTo(arr1, arr2, startIndex) 함수를 작성해보자. compareTo(arr1, arr2, startIndex)는 주석에 작성한 것처럼 한 배열을 기준으로 다른 한 배열과 비교하는 것으로 비교 시작점이 arr1[startIndex], arr2[0]이 된다는 것이 특징이다.

var compareTo(arr1, arr2, index) {
    let maxLength = 0;

    let j = 0;
    let tmpLength = 0;
    for (let i = index; i < arr1.length; i++) {
        if (j >= arr2.length) { break; }
        if (arr1[index] == arr2[j]) {
            tmpLength += 1;
            maxLength = Math.max(maxLength, tmpLength);
        } else {
            tmpLength = 0;
        }
        j += 1;
    }

    return maxLength;
}

 

 

Github: 718.js

opwe37/Algorithm-Study