Today's Challenge

https://leetcode.com/problems/maximum-length-of-repeated-subarray/

Maximum Length of Repeated Subarray - LeetCode

문제를 딱 보는 순간 n이 1000인데 O(n^3)이라서 TLE가 날 거 같아서 무식하게 풀기는 어려워 보임.
아마 슬라이딩 윈도우나 투 포인터를 써야 되는 문제인거 같은데.. 어떻게 코드 작성해야 하는지 기억안남.
그래서 결국 솔루션 엔딩 =_=

------------------------------------------

아니었다. 솔루션 보니 DP로 풀면 되는 문제였음.
Rolling Hash라는걸 이용한 이분 탐색으로 풀어도 됨. 각 세트 자체를 해쉬로 만들어서 비교하는 방법인 듯.

------------------------------------------

DP로 푸는 방법은 생각보다 단순.
메모용 list를 만들고(m * n) 가장 마지막 인덱스부터 시작해서 같은 값이 있을 때마다 증분해주고, 그 중 최대값을 뽑아오면 됨.

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        memo = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
        for i in range(len(nums1) - 1, -1, -1):
            for j in range(len(nums2) - 1, -1, -1):
                if nums1[i] == nums2[j]:
                    memo[i][j] = memo[i+1][j+1] + 1
        return max(max(row) for row in memo)