[LeetCode]Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

text1과 text2가 주어질때 가장 긴 공통 부분 문자열을 구하는 문제입니다.

 

처음 시도한 답안 - 실패

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        text1 = ''.join(sorted(text1))
        text2 = ''.join(sorted(text2))

        min_text = min(text1, text2)
        max_text = max(text1, text2)

        count = 0
        for char in max_text:
            if char in set(min_text):
                count += 1

        return count

접근 방법

1. 처음에 시도했던 방법입니다. 두 문자열을 정렬하여 구하고자 했습니다.
2. text1과 text2 문자열을 정렬합니다.
3. 긴 길이의 문자열을 순회하면서 등장하는 문자가 작은 길이의 문자에도 등장하는지 체크하면서 카운트를 증감합니다.

처음에는 공통 부분 문자열을 정렬하고 동일한 단어가 두 문자열에 등장할 때 카운트를 증감하는 방식으로 구하고자 했습니다. 하지만 "ezupkr", "ubmrapg" 와 같은 예외 케이스가 발생했습니다.

정렬을 함으로써 원래는 subsequence가 아닌 문자열도 subsequence가 되어서 실패했던 풀이입니다.

 

두번째로 시도한 답안

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        text1 = 'O' + text1
        text2 = 'O' + text2

        text1_len = len(text1)
        text2_len = len(text2)

        dp = [[0] * text1_len for _ in range(text2_len)]

        for i in range(1, text2_len):
            for j in range(1, text1_len):
                if text2[i] == text1[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[-1][-1]

접근 방법

1. LCS를 만들기 위해서 2차원 dp를 사용합니다.
2. 두 문자열에 필요없는 O라는 문자를 가장 앞에 붙입니다.
3. 그 후에 문자열의 길이만큼 2차원 dp를 0으로 초기화 합니다.
   1. 이중 순회를 진행하면서
   2. 만약 i,j에서 text2[i]와 text1[j]의 값이 동일하다면 왼쪽 대각선의 dp 값에서 1을 추가합니다.
   3. 아니라면 왼쪽이나 위에 저장된 값에서 큰 값을 선택합니다.
4. 마지막 dp에 가장 긴 공통 부분 문자열의 값이 저장되어 있습니다.

이 문제의 경우 dp 예시를 보면서 설명하는 것이 이해가 더욱 쉽습니다.

	0, O	1, a	2, b	3, d	4, f	5, e
0, O	0	0	0	0	0	0
1, a	0	1	1	1	1	1
2, b	0	1	2	2	2	2
3, e	0	1	2	2	2	3

 

(1,1)의 경우에는 문자열 a와 문자열 a에서 공통 subsequence의 수가 들어가게 됩니다.

예를 들어, (2,4)의 경우라면 ab와 abdf의 공통 subsequence인 "ab" 즉, 2라는 값이 들어가게 됩니다.

 

이렇게 계산을 각 위치에서 계산을 누적하다보면 다음과 같은 규칙을 발견할 수 있습니다.

- 등장한 문자가 같다면 왼쪽 대각선 위의 값에서 +1을 추가
   ((2,2)를 예시로 하면 (1,1)인 a, a 에서 b라는 문자가 붙어 ab, ab가 된 것입니다.)

- 등장한 문자가 다르다면 왼쪽이나 바로 위의 값중 큰 값을 선택

 

또한, 문자열 앞에 불필요한 문자 "O"를 붙여줌으로써 위와 같은 규칙을 만들어 낼 수 있습니다. O을 붙이지 않고 문자열보다 1개 더 긴 dp를 만드는 방법도 가능합니다.

하지만, 문자열 길이만큼만 2차원 리스트를 선언한다면 첫번째 규칙을 찾는 과정에서 index를 벗어나게 되고 이로 인해 불편한 처리 과정이 생기게 됩니다.

LCS 문제의 경우 DP를 활용한 정형화된 풀이 방법이 존재하기에 숙지해두면 좋을 것 같습니다.

이전에도 문제를 풀었는데 기억이 나지 않아서 솔루션을 다시 참고했었습니다.

https://leffept.tistory.com/264

[백준]9251번 LCS - DP