세 번째 문자열과 스왑하여 두 문자열을 동일하게 만들 수 있는지 확인하는 C++ 프로그램

문제 설명

길이가 모두 n으로 같은 세 개의 문자열 S, T, U가 주어졌다고 가정해 봅시다. 인덱스 0부터 n-1까지의 각 위치 i에서, 우리는 U[i]를 S[i] 또는 T[i] 중 하나와 맞바꾸어야(swap) 합니다. 즉, 총 n번의 스왑 연산을 수행하게 됩니다. 문제의 목표는 이러한 연산을 모두 마친 뒤에 문자열 S를 T와 완전히 동일하게 만들 수 있는지 판별하는 것입니다.

예를 들어 입력이 S = 'abc', T = 'bca', U = 'bca'라고 해봅시다. 이 경우 출력은 True가 됩니다. 모든 인덱스 i에서 U[i]를 S[i]와 맞바꾸면 S는 'bca'가 되고, T 역시 이미 'bca'이므로 두 문자열이 정확히 일치하기 때문입니다.

해결 접근 방식

이 문제는 각 인덱스를 순차적으로 검사하는 방식으로 간단히 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 어떤 인덱스 i에서 U[i]가 S[i]와도 T[i]와도 일치하지 않는다면, 해당 위치에서 어떤 스왑을 선택하더라도 두 문자열을 일치시키는 것은 불가능합니다. 따라서 모든 인덱스에서 U[i]가 S[i] 또는 T[i] 중 적어도 하나와 일치해야만 성공적인 결과를 얻을 수 있습니다.

이를 의사 코드로 표현하면 다음과 같습니다.

i := 0부터 시작하여 S의 끝까지 반복:
    만약 S[i] != U[i] 이고 T[i] != U[i]라면:
        false 반환
반복이 끝나면 true 반환

예제 코드

아래의 C++ 구현 예제를 통해 더 자세히 이해해 보겠습니다.

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

bool solve(string S, string T, string U) {
    for (int i = 0; S[i]; ++i)
        if (S[i] != U[i] && T[i] != U[i])
            return false;
    return true;
}

int main() {
    string S = "abc";
    string T = "bca";
    string U = "bca";
    cout << solve(S, T, U) << endl;
}

입력

"abc", "bca", "bca"

출력

1

실행 결과 solve 함수가 1(true)을 반환했습니다. 이는 세 문자열이 위에서 설명한 조건을 모두 만족하므로, n번의 스왑 연산만으로 S를 T와 동일하게 만들 수 있음을 의미합니다. 이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)으로 매우 효율적입니다.