Daily LeetCode Challenge - 1035. Uncrossed Lines

Problem From.

https://leetcode.com/problems/uncrossed-lines/

오늘 문제는 두개의 리스트가 주어질때, 각각 같은 원소끼리 줄을 그었을때, 그 줄이 겹치지 않는 최대의 줄 수를 구하는 문제였다.

이 문제는 DP 를 이용해서 푸는 문제였는데, 그 전의 결과를 다음 결과에 쌓아서 보여주면 되었다.
가장 기본적인 아이디어는, 긴 쪽에서 짧은쪽의 원소를 검사하면서, 원소가 같으면, 그 전의 같은 수에서 +1 을 해주면 되고, 아니라면, 이미 저장되어 있던 데이터와 현재 연결된 수를 비교해서 최대값을 쌓아나가는 식으로 풀이하였다.

class Solution {
    fun maxUncrossedLines(nums1: IntArray, nums2: IntArray): Int {
        var s = nums1.size
        var l = nums2.size
        var shortArray = nums1
        var longArray = nums2
        if(s > l) {
            s = nums2.size
            l = nums1.size
            shortArray = nums2
            longArray = nums1
        }
        val memo = Array(s + 1) { 0 }
        for(i in 1..l) {
            var prev = 0
            for(j in 1..s) {
                val curr = memo[j]
                if(longArray[i - 1] == shortArray[j - 1]) {
                    memo[j] = prev + 1
                }else {
                    memo[j] = Math.max(memo[j-1], curr)
                }
                prev = curr
            }
        }
        return memo[s]
    }
}