🧶 초보자용 가이드 ‘Minimum ASCII Delete Sum for Two Strings’ – LeetCode 712 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

주어진 것:

• 두 문자열 s1와 s2.

목표:

• 두 문자열을 동일하게 만들기 위해 삭제해야 하는 문자들의 ASCII 합을 최소화한다.

Source: …

직관

이 문제는 최장 공통 부분수열 (LCS) 혹은 편집 거리(Edit Distance) 문제의 변형이라고 볼 수 있습니다. 핵심 아이디어는 각 문자 쌍에 대해 두 문자열을 동일하게 만들기 위해 해당 문자를 유지할지 삭제할지를 결정하는 것입니다.

우리는 동적 프로그래밍(DP) 과 메모이제이션을 사용하여 이러한 선택을 탐색합니다:

1. 기본 경우 – 한 문자열의 끝에 도달하면, 다른 문자열에 남아 있는 모든 문자를 삭제하는 것만이 두 문자열을 동일하게 만들 수 있는 방법입니다. 남은 문자들의 ASCII 값을 모두 더한 값을 비용으로 반환합니다.
2. 일치 – s1[i]와 s2[j]가 동일하면, 이를 유지하는 데 비용이 0입니다. 단순히 다음 문자 쌍으로 이동합니다.
3. 불일치 – 문자가 일치하지 않을 경우, 두 가지 주요 선택이 있습니다:
   • s1[i]를 삭제하고(그 ASCII 값을 비용으로) 나머지 s1과 현재 s2를 비교합니다.
   • s2[j]를 삭제하고(그 ASCII 값을 비용으로) 현재 s1과 나머지 s2를 비교합니다.
4. 최적화 – 항상 최소 합을 제공하는 경로를 선택합니다. 결과를 2‑차원 배열(dp)에 저장함으로써 동일한 부분 문제를 여러 번 다시 계산하는 것을 피합니다.

코드 블록

C++ 솔루션

class Solution {
public:
    int helper(string& s1, string& s2, int i, int j, vector>& dp) {
        int n = s1.size();
        int m = s2.size();

        // If s1 is exhausted, delete remaining characters of s2
        if (i == n) {
            int sum = 0;
            for (int k = j; k > dp(n, vector(m, -1));
        return helper(s1, s2, 0, 0, dp);
    }
};

파이썬 솔루션

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n, m = len(s1), len(s2)
        dp = [[-1] * m for _ in range(n)]

        def helper(i, j):
            # Base case: s1 exhausted
            if i == n:
                return sum(ord(c) for c in s2[j:])
            # Base case: s2 exhausted
            if j == m:
                return sum(ord(c) for c in s1[i:])

            if dp[i][j] != -1:
                return dp[i][j]

            if s1[i] == s2[j]:
                dp[i][j] = helper(i + 1, j + 1)
            else:
                # Compare cost of deleting from s1 vs deleting from s2
                delete_s1 = ord(s1[i]) + helper(i + 1, j)
                delete_s2 = ord(s2[j]) + helper(i, j + 1)
                dp[i][j] = min(delete_s1, delete_s2)

            return dp[i][j]

        return helper(0, 0)

자바스크립트 솔루션

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function (s1, s2) {
    const n = s1.length;
    const m = s2.length;
    const dp = Array.from({ length: n }, () => Array(m).fill(-1));

    function helper(i, j) {
        // Base case: s1 exhausted
        if (i === n) {
            let sum = 0;
            for (let k = j; k < m; ++k) sum += s2.charCodeAt(k);
            return sum;
        }
        // Base case: s2 exhausted
        if (j === m) {
            let sum = 0;
            for (let k = i; k < n; ++k) sum += s1.charCodeAt(k);
            return sum;
        }

        if (dp[i][j] !== -1) return dp[i][j];

        if (s1[i] === s2[j]) {
            dp[i][j] = helper(i + 1, j + 1);
        } else {
            // Minimum of deleting s1[i] or s2[j]
            const deleteS1 = s1.charCodeAt(i) + helper(i + 1, j);
            const deleteS2 = s2.charCodeAt(j) + helper(i, j + 1);
            dp[i][j] = Math.min(deleteS1, deleteS2);
        }
        return dp[i][j];
    }

    return helper(0, 0);
};

Key Takeaways

• Memoization: 2‑D 배열에 결과를 캐시함으로써 시간 복잡도를 지수형에서 O(n · m) 으로 줄인다, 여기서 n과 m은 두 문자열의 길이이다.
• ASCII Mapping: 문자 값은 단순한 레이블이 아니다. Python의 ord()나 JavaScript의 charCodeAt()을 사용하면 텍스트를 최적화를 위한 수치 데이터로 다룰 수 있다.
• Decision Trees: 이 문제는 선택(s1 삭제 vs. s2 삭제)을 재귀 호출 트리로 모델링하고 DP로 효율적으로 가지치기하는 방법을 가르쳐준다.

최종 생각

Minimum ASCII Delete Sum 문제는 겉보기에 단순한 문자열‑조작 작업을 동적‑프로그래밍 과제로 바꾸는 전형적인 예시입니다. 기본이 되는 LCS‑스타일 재귀 관계를 이해하고 메모이제이션을 적용하면 어떤 언어에서도 효율적으로 해결할 수 있습니다.

표준 알고리즘에 약간의 수정을 가하면 적용 분야가 달라질 수 있습니다. 실제‑세계 소프트웨어 엔지니어링에서는 이 논리가 Bioinformatics(생물정보학)에서 DNA 서열을 정렬하거나 Version Control Systems(예: Git)에서 두 파일 버전 간의 diff를 계산하는 데 사용됩니다. 이러한 가중‑문자열 문제를 마스터하면 검색 엔진이나 비교 도구를 구축할 때 훨씬 더 효과적으로 작업할 수 있습니다.