Uncrossed Lines(Array,Dynamic Programming)

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

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.

 

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

 

Constraints:

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

항상 짜증을 주는 그녀,

 

Dynamic Programming 문제이다.

 

냅다 함 풀어봅시다.

 

문제는 무슨 소린지 알겠는데, 도저히 DP적으로 풀 수가 없을 거 같다..

 

Hint를 봐도 어려운 것이 현실.. 아나 이거 그냥 보자마자 DP로 풀 능력자들도 있겠지..?

Hint 1   Think dynamic programming. Given an oracle dp(i,j) that tells us how many lines A[i:], B[j:] [the sequence A[i], A[i+1], ... and B[j], B[j+1], ...] are uncrossed, can we write this as a recursion?

 

GG쳤다..

 

1. Python

봐도 모르겄다..

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1),len(nums2)
        # DP initialize
        dp = [[0]*(n+1) for _ in range(m+1)] # m+1 * n+1 matrix
        # Fill DP
        for i in range(1,m+1):
            for j in range(1,n+1):
                if nums1[i-1] == nums2[j-1]:
                    # if elements match, add 1 to the result of excluding these elements
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    # O.W take the maximum of excluding the current element
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[m][n]

 

 

2. C++

 

DP C++로도 풀어보기.

Solution을 보아하니 LCS와 비슷한 유형의 문제라던데 참.. 오 놀라워라 그댈 향한 내 마음..

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        
        vector<vector<int>> dp(m+1,vector<int>(n+1,0)); // m+1 * n+1
        for(int i=1;i<=m;i++){
            for(int 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] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

 

아 짜증나게 어렵네 진짜..

 

다시 비슷한 유형의 문제가 나왔을 때 풀 자신이 없다..

 

 

그리하여.. 이 논리를 이해했는지 LCD 문제를 풀어본다.

 

자가진단 문제: Longest Common Subsequence (LCS)

문제 설명

두 문자열 text1과 text2가 주어졌을 때, 두 문자열의 **가장 긴 공통 부분 수열 (Longest Common Subsequence, LCS)**의 길이를 구하세요.
공통 부분 수열은 문자열의 순서를 유지하며 각 문자열에서 문자를 선택해 만들 수 있는 수열입니다.
예를 들어, text1 = "abcde"와 text2 = "ace"의 LCS는 "ace"이며 길이는 3입니다.

---

입력

• text1과 text2는 모두 알파벳 소문자로 이루어진 문자열입니다.
• 1 <= text1.length, text2.length <= 1000

---

출력

• 두 문자열의 가장 긴 공통 부분 수열의 길이를 반환합니다.

---

예제

Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: LCS는 "ace"이며, 길이는 3입니다.

Input: text1 = "abc", text2 = "def" Output: 0 Explanation: 공통 부분 수열이 없으므로 길이는 0입니다.

 

 

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # DP 테이블 초기화 및 로직 작성
        m = len(text1)
        n = len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[m][n]

# 테스트 케이스
if __name__ == "__main__":
    solution = Solution()
    # Example test cases
    print(solution.longestCommonSubsequence("abcde", "ace"))  # Output: 3
    print(solution.longestCommonSubsequence("abc", "def"))   # Output: 0
    print(solution.longestCommonSubsequence("abc", "abc"))   # Output: 3
    print(solution.longestCommonSubsequence("abcd", "abdc")) # Output: 3

 

이번엔 일전에 다루었던, LCS의 최대 길이가 아닌 LCS 그 자체를 반환하는데 길이가 같은 것이 여러개 있을 경우엔 알파벳 순으로 가장 빠른 녀석을 반환 ex) aaa / bbb 있으면 aaa를 반환하게 코딩!

"""
이제 LCS의 길이를 반환하는 대신, 가장 긴 공통 부분 수열(LCS) 자체를 반환하도록 코드를 수정했습니다. 또한, LCS가 여러 개 존재할 경우 알파벳 순으로 가장 작은 LCS를 선택합니다.
"""
"GPT 풀이"

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> str:
        m = len(text1)
        n = len(text2)
        dp = [[""]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + text1[i-1]
                else:
                    if len(dp[i-1][j]) > len(dp[i][j-1]) : dp[i][j] = dp[i-1][j]
                    elif len(dp[i-1][j]) < len(dp[i][j-1]) : dp[i][j] = dp[i][j-1]
                    else: dp[i][j] = min(dp[i][j-1],dp[i-1][j])
        return dp[m][n]
# 테스트 케이스
if __name__ == "__main__":
    solution = Solution()
    # Example test cases
    print(solution.longestCommonSubsequence("abcde", "ace"))  # Output: "ace"
    print(solution.longestCommonSubsequence("abc", "def"))   # Output: ""
    print(solution.longestCommonSubsequence("abc", "abc"))   # Output: "abc"
    print(solution.longestCommonSubsequence("abcd", "abdc")) # Output: "abc"
    print(solution.longestCommonSubsequence("abdc", "abcd")) # Output: "abc"
    print(solution.longestCommonSubsequence("aaczzcas", "cazia")) # Output: "aza"

 

위 풀이가 최선인듯 하다..