[leet code] 1092. Shortest Common Supersequence (JAVA)

이형걸·2025년 2월 28일

Shortest Common Subsequence dynamic programming scs

Problem Solving

목록 보기

19/23

[leet code] 1092. Shortest Common Supersequence

🗒️알고리즘 분류

#Dynamic Programming #SCS #Shortest Common Subsequence

DP 로 보는 SCS

1. dp[i][j]의 정의

dp[i][j]는 str1의 i번째 문자까지 고려하고, str2의 j번째 문자까지 고려했을 때 가능한 공통 subsequence(Shortest Common subsequence, SCS)의 최소 길이를 나타냅니다.
- 여기서 i와 j는 각각 문자열의 접두사(prefix) 길이를 의미합니다.
- 예를 들어, dp[3][2]는 str1의 첫 3문자와 str2의 첫 2문자를 모두 부분 수열로 갖는 SCS의 최소 길이를 의미합니다.
이 dp 테이블을 채우면, 최종적으로 dp[str1.length()][str2.length()] 가 전체 문자열에 대한 SCS의 길이가 됩니다.

2. 점화식 및 base case

(A) 문자가 같은 경우:

조건: if (str1[i-1] == str2[j-1])
설명:두 문자열의 현재 문자가 동일하다면, 이 문자는 한 번만 포함하면 됩니다.
따라서 dp[i][j] = dp[i-1][j-1] + 1 → 즉, 이전 상태의 SCS에 공통 문자를 한 번 추가합니다.

(B) 문자가 다른 경우:

조건: if (str1[i-1] != str2[j-1])
설명: 두 문자열의 현재 문자가 다르다면, SCS는 두 문자열 모두의 문자를 모두 포함해야 하므로 어느 한쪽의 문자를 추가하는 두 가지 경우를 고려합니다.
- 옵션 1: SCS를 만들 때 str1의 현재 문자인 str1[i-1]을 추가하는 경우
  - → SCS의 길이는 dp[i-1][j]에 str1[i-1]을 추가한 것이므로 dp[i-1][j] + 1
- 옵션 2: SCS를 만들 때 str2의 현재 문자인 str2[j-1]을 추가하는 경우
  - → SCS의 길이는 dp[i][j-1]에 str2[j-1]을 추가한 것이므로 dp[i][j-1] + 1

2-1. Base Case 초기화

초기화 단계에서는 두 문자열 중 한쪽이 빈 문자열인 경우를 처리합니다.

dp[i][0] = i:
- 여기서 i (row)는 str1의 접두사 길이를 나타냅니다.
- 만약 str2가 빈 문자열(즉, j = 0)라면, SCS는 오직 str1의 첫 i 문자 그대로밖에 없으므로 길이는 i가 됩니다.
- 예를 들어, str1 = "abc"이고 str2가 빈 문자열이라면, SCS는 "abc"가 되어 길이가 3입니다. 따라서 dp[3][0] = 3.
dp[0][j] = j:
- 여기서 j (col)는 str2의 접두사 길이를 나타냅니다.
- 만약 str1이 빈 문자열(즉, i = 0)이라면, SCS는 str2의 첫 j 문자 그대로이므로 길이는 j가 됩니다.
- 예를 들어, str2 = "def"이고 str1이 빈 문자열이라면, SCS는 "def"가 되어 길이가 3입니다. 따라서 dp[0][3] = 3.

3. 왜 dp[i][0] = i 인가?

상황 설명: dp[i][0]는 str1의 첫 i 문자와 str2의 빈 문자열을 이용해 만든 SCS의 길이입니다.
이유:
- str2가 빈 문자열이면, 공통 초서열을 만들 때 str2에서 추가할 문자가 없습니다.
- 따라서 SCS는 단순히 str1의 첫 i 문자가 그대로 SCS가 됩니다.
- 문자열 str1의 접두사 길이가 i이면, 그 길이는 자연스럽게 i가 됩니다.
비유: 예를 들어, str1 = "hello"이고 str2가 ""인 경우, SCS는 "hello"가 되어 길이가 5입니다. 그래서 dp[5][0] = 5가 되는 것입니다.

4. 왜 문자가 다를 때도 +1을 하는가?

SCS는 두 문자열 모두의 문자를 포함해야 하므로 만약 str1[i-1]와 str2[j-1]가 같지 않다면, 두 문자열의 현재 문자를 모두 포함해야 합니다. 그러나 SCS에서는 두 문자를 따로 추가할 필요 없이 하나만 추가하면서 나중에 나머지 문자를 포함하는 선택을 하게 됩니다.
예시:
- str1의 접두사가 "ab"이고, str2의 접두사가 "ac"인 경우를 생각해봅시다.
- dp[2][2]를 구하기 위해
  - 옵션 1: "ab"와 "a"에서 만든 SCS에 str1[1] = 'b'를 추가 → 길이 = dp[1][2] + 1
  - 옵션 2: "ab"와 "a"에서 만든 SCS에 str2[1] = 'c'를 추가 → 길이 = dp[2][1] + 1
  - 이 때, 두 옵션 중 짧은 길이를 선택하게 됩니다.
즉, 문자가 같으면 한 번만 추가하고, 다르면 어느 한쪽을 선택하므로 추가된 문자는 1개이고 그 선택을 위해 +1을 하는 것입니다.
왜 짧은 쪽?
- SCS의 최종 목표는 최소 길이이기 때문에,두 옵션 중 더 짧은 결과를 주는 선택이 전체 SCS의 길이를 최소화합니다.

5. 왜 역방향인가?

DP 테이블을 채울 때, base case부터 시작하여 최종 dp[m][n]까지 계산합니다.
하지만, 어떤 선택이 이루어졌는지 결정하는 것은 최종 상태에서부터 역으로 추적해야 합니다.
예를 들어, dp[m][n]의 값이 dp[m-1][n] + 1인지, 아니면 dp[m][n-1] + 1인지, 또는 dp[m-1][n-1] + 1인지를 확인해야 합니다.
이러한 결정은 dp[m][n]에서 시작해 거꾸로 이동하면서, 실제로 어떤 문자가 SCS에 포함되었는지 결정됩니다.
이렇게 추적하면, 선택한 문자들이 뒤에서부터 쌓이게 되어 최종적으로 문자열을 뒤집어야 올바른 순서가 됩니다.
정방향으로 재구성하는 것과의 차이
- 정방향으로 SCS를 구성하려면, DP 테이블에 경로 정보(선택한 문자 또는 포인터)를 별도로 저장해야 합니다.
- 그렇지 않으면, dp[i][j]만으로는 "어떤 문자가 언제 선택되었는지"를 알 수 없으므로, 정방향 재구성이 어렵습니다.
- 따라서, 일반적으로는 dp 테이블을 다 채운 후, 역방향 추적을 통해 SCS 문자열을 복원하고, 최종 결과를 reverse()로 뒤집어 올바른 순서를 얻습니다.

📝풀이 코드 (JAVA)

import java.util.*;

class Solution {

    public String shortestCommonSupersequence(String str1, String str2) {
        int str1Length = str1.length();
        int str2Length = str2.length();

        // dp[row][col] : str1의 첫 row, str2의 첫 col로 만들 수 있는 SCS의 길이
        int[][] dp = new int[str1Length + 1][str2Length + 1];

        // Base case: 한쪽이 빈 문자열일 때의 SCS 길이
        for (int row = 0; row <= str1Length; row++) {
            dp[row][0] = row;
        }
        for (int col = 0; col <= str2Length; col++) {
            dp[0][col] = col;
        }

        // DP 테이블 채우기
        for (int row = 1; row <= str1Length; row++) {
            for (int col = 1; col <= str2Length; col++) {
                if (str1.charAt(row - 1) == str2.charAt(col - 1)) {
                    dp[row][col] = dp[row - 1][col - 1] + 1;
                } else {
                    dp[row][col] = Math.min(dp[row - 1][col], dp[row][col - 1]) + 1;
                }
            }
        }

        // Backtracking을 통해 SCS 재구성
        StringBuilder supersequence = new StringBuilder();
        int row = str1Length, col = str2Length;

        while (row > 0 && col > 0) {
            if (str1.charAt(row - 1) == str2.charAt(col - 1)) {
                // 문자가 같으면, 해당 문자를 결과에 추가하고 대각선으로 이동
                supersequence.append(str1.charAt(row - 1));
                row--;
                col--;
            } else if (dp[row - 1][col] < dp[row][col - 1]) {
                // str1의 문자를 포함하는 쪽이 더 짧다면
                supersequence.append(str1.charAt(row - 1));
                row--;
            } else {
                // 그렇지 않으면, str2의 문자를 포함하는 쪽으로 이동
                supersequence.append(str2.charAt(col - 1));
                col--;
            }
        }

        // 남은 문자 처리 (한쪽 문자열이 남은 경우)
        while (row > 0) {
            supersequence.append(str1.charAt(row - 1));
            row--;
        }
        while (col > 0) {
            supersequence.append(str2.charAt(col - 1));
            col--;
        }

        // 결과 문자열은 역순으로 구성되었으므로 뒤집어서 반환
        return supersequence.reverse().toString();
    }
}