Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 두 문자열의 최소 ASCII 삭제 합계 구하기

문제 개요

두 개의 문자열 w1과 w2가 주어졌을 때, 각 단계마다 어느 한쪽 문자열에서 문자를 하나씩 삭제할 수 있다고 가정해 봅시다. 이때 두 문자열을 완전히 동일하게 만들기 위해 삭제해야 하는 문자들의 ASCII 값 합계의 최솟값을 구하는 것이 이번 문제의 목표입니다.

예를 들어 입력이 "sea"와 "eat"이라면 출력은 231이 됩니다. 그 이유는 다음과 같습니다.

  • w1에서 's'(ASCII 115)를 삭제하면 "ea"가 됩니다.
  • w2에서 't'(ASCII 116)를 삭제하면 "ea"가 됩니다.
  • 두 문자열이 같아지며, 총합은 115 + 116 = 231로 이것이 가능한 최솟값입니다.

접근 방법: 동적 계획법(DP)

이 문제는 대표적인 동적 계획법(Dynamic Programming) 유형으로, 편집 거리(Edit Distance) 문제와 매우 유사한 구조를 가집니다. 차이점은 연산 비용이 고정된 값이 아니라 삭제하는 문자의 ASCII 값이라는 점입니다.

해결 과정은 다음과 같습니다.

  1. n := s1의 길이, m := s2의 길이로 설정합니다.
  2. 인덱스 계산을 편하게 하기 위해 s1과 s2 앞에 공백 한 칸을 추가합니다.
  3. (n + 1) × (m + 1) 크기의 DP 테이블을 생성합니다.
  4. 초기화: i := 1부터 m까지 dp[0][i] := dp[0][i-1] + s2[i]
  5. 초기화: i := 1부터 n까지 dp[i][0] := dp[i-1][0] + s1[i]
  6. i를 1부터 n까지, j를 1부터 m까지 순회하면서:
    • s1[i] == s2[j]라면 → dp[i][j] := dp[i-1][j-1] (문자를 유지하고 비용 없이 진행)
    • 그렇지 않다면 → dp[i][j] := min(dp[i-1][j] + s1[i], dp[i][j-1] + s2[j]) (어느 쪽 문자를 삭제할지 더 작은 비용 선택)
  7. 최종적으로 dp[n][m]을 반환합니다.

여기서 dp[i][j]는 s1의 처음 i개 문자와 s2의 처음 j개 문자를 같게 만들기 위한 최소 삭제 비용을 의미합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumDeleteSum(string s1, string s2) {
      int n = s1.size();
      int m = s2.size();
      s1 = " " + s1;
      s2 = " " + s2;
      vector < vector <int> > dp(n + 1, vector <int>(m + 1));
      for(int i = 1; i <= m; i++){
         dp[0][i] = dp[0][i - 1] + s2[i];
      }
      for(int i = 1; i <= n; i++){
         dp[i][0] = dp[i - 1][0] + s1[i];
      }
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s1[i] == s2[j]){
               dp[i][j] = dp[i - 1][j - 1];
            }
            else{
               dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j]);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.minimumDeleteSum("sea", "eat"));
}

실행 결과 확인

입력:

"sea"
"eat"

출력:

231

복잡도 분석

이 알고리즘의 시간 복잡도는 DP 테이블의 모든 칸을 한 번씩 채우므로 O(n × m)이며, 공간 복잡도 역시 테이블 저장에 필요한 O(n × m)입니다. 여기서 n과 m은 각각 두 문자열의 길이입니다.