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

C++로 한 문자열을 다른 문자열로 변환하는 최소 삭제·삽입 횟수 구하기

문제 설명

두 개의 문자열 str1(길이 m)과 str2(길이 n)가 주어집니다. 목표는 str1에서 문자를 삭제하거나 삽입하여 str1을 str2로 변환할 때, 필요한 삭제와 삽입 연산의 횟수를 최소화하는 것입니다.

str1 = "tutorialspoint"
str2 = "tutorials"

str1을 str2로 변환하려면 5개의 문자,
즉 "point"를 str1에서 삭제하면 됩니다.

접근 방법

핵심 아이디어는 두 문자열의 최장 공통 부분 수열(LCS, Longest Common Subsequence)을 활용하는 것입니다. LCS에 포함된 문자들은 순서가 서로 일치하므로 그대로 유지하고, 나머지 문자만 삭제하거나 삽입하면 되기 때문입니다.

  1. str1과 str2의 최장 공통 부분 수열 길이를 구합니다. 이를 lcsSize라고 합니다.
  2. 삭제해야 할 문자 수 = str1의 길이 − lcsSize
  3. 삽입해야 할 문자 수 = str2의 길이 − lcsSize

C++ 구현 예제

아래 코드는 재귀 호출로 LCS 길이를 계산한 뒤, 최소 삭제 횟수와 최소 삽입 횟수를 출력합니다.

#include <iostream>
#include <algorithm>
using namespace std;

// 두 문자열의 최장 공통 부분 수열(LCS) 길이를 재귀적으로 계산
int lcs(string s1, string s2, int m, int n){
    if (m == 0 || n == 0) {
        return 0;
    }
    if (s1[m - 1] == s2[n - 1]) {
        return 1 + lcs(s1, s2, m - 1, n - 1);
    } else {
        return max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
    }
}

// 최소 삭제 횟수와 최소 삽입 횟수를 계산하여 출력
void minDeletionAndInsertion(string s1, string s2){
    int m = s1.size();
    int n = s2.size();
    int lcsSize = lcs(s1, s2, m, n);
    cout << "Min deletion = " << (m - lcsSize) << endl;
    cout << "Min insertion = " << (n - lcsSize) << endl;
}

int main(){
    minDeletionAndInsertion("tutorialspoint", "tutorials");
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Min deletion = 5
Min insertion = 0

동작 원리 살펴보기

"tutorialspoint"(길이 14)와 "tutorials"(길이 9)의 LCS는 "tutorials"로 길이가 9입니다. 따라서 삭제 횟수는 14 − 9 = 5, 삽입 횟수는 9 − 9 = 0이 됩니다. 즉, 공통 부분인 "tutorials"는 그대로 두고 "point"만 삭제하면 변환이 완료됩니다.

성능 개선 팁

위 재귀 구현은 중복 계산이 많아 최악의 경우 지수 시간이 걸릴 수 있습니다. 실무에서는 메모이제이션(memoization)이나 동적 계획법(DP) 테이블을 적용하면 O(m×n) 시간 복잡도로 효율적으로 해결할 수 있으니, 입력 크기가 클 때는 DP 기반 구현을 사용하는 것이 좋습니다.