C++로 문자열을 회문으로 만들기 위한 최소 삽입 횟수 구하기

문자열 s가 주어졌을 때, 이 문자열을 회문(palindrome)으로 만들어야 한다고 가정해 봅시다. 각 단계에서 임의의 위치에 임의의 문자를 삽입할 수 있으며, 회문을 만들기 위해 필요한 최소 삽입 횟수를 구하는 것이 목표입니다.

예를 들어 문자열이 "mad"라면, 앞에 "da"를 추가하여 "damad"를 만들거나 뒤에 "am"을 추가하여 "madam"을 만들 수 있으므로 정답은 2가 됩니다.

해결 접근 방식: 최장 공통 부분 수열(LCS) 활용

이 문제는 동적 계획법(DP)을 이용한 최장 공통 부분 수열(Longest Common Subsequence, LCS) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

주어진 문자열 s와 그것을 뒤집은 문자열 x 사이의 LCS 길이를 구합니다.
LCS는 원래 문자열에서 이미 회문의 성질을 만족하는 가장 긴 부분을 의미합니다.
따라서 필요한 최소 삽입 횟수는 (문자열 길이 − LCS 길이)입니다.

알고리즘 단계

lcs() 함수를 정의하고, 매개변수로 문자열 s를 받은 뒤 x := s로 초기화합니다.
n := 문자열 s의 길이로 설정합니다.
문자열 x를 뒤집습니다.
s와 x 앞에 공백 한 칸을 붙여 인덱스를 1부터 시작하도록 조정합니다.
(n + 1) × (n + 1) 크기의 2차원 배열 dp를 선언합니다.
i := 1부터 n까지 반복하면서 다음을 수행합니다.
- j := 1부터 n까지 반복하면서 다음을 수행합니다.
  - dp[i][j] := dp[i-1][j]와 dp[i][j-1] 중 최댓값으로 설정합니다.
  - 만약 s[i]와 x[j]가 같다면, dp[i][j] := max(dp[i][j], dp[i-1][j-1] + 1)로 갱신합니다.
dp[n][n] 값을 반환합니다.

마지막으로 메인 로직에서는 문자열 s의 길이에서 lcs(s)의 결과를 뺀 값을 반환하면 됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int lcs(string s){
        string x = s;
        int n = s.size();
        reverse(x.begin(), x.end());
        s = " " + s;
        x = " " + x;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if(s[i] == x[j]){
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[n][n];
    }
    int minInsertions(string s) {
        return s.size() - lcs(s);
    }
};
main(){
    Solution ob;
    cout << (ob.minInsertions("mad"));
}

입력

"mad"

출력

시간 복잡도 분석

이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)이며, 2차원 DP 배열을 사용하므로 공간 복잡도 역시 O(n²)입니다. 여기서 n은 문자열의 길이입니다.