Uncrossed Lines

HS K·2023년 5월 11일

문제설명

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j]such that:

nums1[i] == nums2[j], and
the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

제한사항

1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

입출력 예

Example 1:

Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.

Example 2:

Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3

Example 3:

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

행동영역(알고리즘을 설계하는 사고과정)

답

내가 쓴 답

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxUncrossedLines = function(nums1, nums2) {
    let arr = []
    for (let i = 0; i < nums1.length; i++) {
    if (nums2.indexOf(nums1[i]) !== -1) {
      arr.push(nums2.indexOf(nums1[i]));
    }
  }

  const result = arr.reduce((acc, curr, i) => {
    if (i === 0 || arr[i - 1] <= arr[i]) {
      acc.push(arr[i]);
    }
    return acc;
  }, []);

  return result.length;
};

하지만 nums1 = [2,5,1,2,5], num2=[10,5,2,1,5,2] 일때 indexOf()를 이용하여 선을 긋는 작업에서 [ 2, 1, 3, 2, 1 ] 요소가 중복되는 경우 index도 중복되는 경우를 고려해주지 못했다.

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxUncrossedLines = function(nums1, nums2) {
let m = nums1.length;
    let n = nums2.length;
    let dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    for(let i = 1; i <= m; i++) {
        for(let j = 1; j <= n; j++) {
            if(nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
};

다른풀이

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const maxUncrossedLines = function(nums1, nums2) {
    let matrix = new Array(nums1.length + 1).fill();
    for(let i = 0; i < matrix.length - 1; i++) {
        matrix[i] = new Uint16Array(nums2.length + 1).fill();
        matrix[i][matrix[i].length - 1] = 0;
    }
   
    matrix[nums1.length] = new Uint16Array(nums2.length + 1).fill(0);
 


    for(let i = nums1.length - 1; i >= 0; i--) {
        for(let j = nums2.length - 1; j >= 0; j--) {

            if(nums1[i] === nums2[j]) {
                matrix[i][j] = matrix[i + 1][j + 1] + 1;
            } else {
                matrix[i][j] = Math.max(matrix[i + 1][j], matrix[i][j + 1]);
            };

        };
    };

    return matrix[0][0];
};