C++ 문자열 변환: append와 delete 연산으로 한 문자열을 다른 문자열로 바꾸는 방법

이 튜토리얼에서는 append(추가)와 delete(마지막 요소 삭제) 연산만을 사용하여 하나의 문자열을 다른 문자열로 변환할 수 있는지 판별하는 프로그램을 다룹니다.

두 개의 문자열이 주어졌을 때, 우리의 목표는 정확히 k번의 추가 및 삭제 연산을 수행하여 첫 번째 문자열을 두 번째 문자열로 변환하는 것이 가능한지 계산하는 것입니다.

문제 해결 접근 방식

이 문제를 해결하려면 다음과 같은 논리를 적용합니다.

먼저 두 문자열 길이의 합이 k보다 작은 경우를 확인합니다. 이 경우 남은 연산 횟수를 모두 소모하여 조건을 만족시킬 수 있으므로 변환이 가능합니다.

다음으로 두 문자열의 공통 접두사(prefix) 길이를 구합니다. 공통 부분은 유지하고 나머지 부분만 삭제 후 새로 추가하면 되기 때문입니다.

필요한 최소 연산 횟수는 다음과 같이 계산됩니다.

최소 연산 = str1.length() + str2.length() - 2 * commonLength

남은 연산 횟수(k에서 최소 연산을 뺀 값)가 짝수라면, 불필요한 추가-삭제 쌍을 반복하여 정확히 k번의 연산을 맞출 수 있습니다. 따라서 이 값이 짝수인지 확인하면 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 두 문자열 간의 변환 가능 여부 확인
bool if_convert(string str1, string str2, int k) {
    // 두 문자열 길이의 합이 k보다 작으면 항상 가능
    if ((str1.length() + str2.length()) < k)
        return true;

    // 두 문자열의 공통 접두사 길이 계산
    int commonLength = 0;
    for (int i = 0; i < min(str1.length(), str2.length()); i++) {
        if (str1[i] == str2[i])
            commonLength++;
        else
            break;
    }

    // 남은 연산 횟수가 짝수인지 확인
    if ((k - str1.length() - str2.length() +
        2 * commonLength) % 2 == 0)
        return true;

    return false;
}

int main() {
    string str1 = "tutorials", str2 = "point";
    int k = 5;

    if (if_convert(str1, str2, k))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

실행 결과

No

코드 설명

위 예제에서 첫 번째 문자열 "tutorials"(길이 9)를 두 번째 문자열 "point"(길이 5)로 k=5번의 연산으로 변환해야 합니다. 두 문자열의 공통 접두사는 없으므로 최소 14번의 연산이 필요하지만, 주어진 연산 횟수는 5번뿐입니다. 또한 남은 연산 횟수도 짝수가 아니므로 프로그램은 No를 출력합니다.

이 알고리즘의 시간 복잡도는 O(n)으로, 두 문자열 중 더 짧은 길이에 비례하여 선형적으로 증가합니다.