C++ 메타 문자열 판별하기: 문자 하나를 교환했을 때 두 문자열이 같아지는지 확인하는 방법

메타 문자열(Meta String)이란?

이번 글에서는 두 문자열이 메타 문자열인지 확인하는 방법을 알아보겠습니다. 메타 문자열이란 서로 매우 유사한 문자열로, 한쪽 문자열에서 단 두 개의 문자 위치를 맞바꾸면 다른 문자열과 완전히 일치하게 되는 관계를 말합니다.

예를 들어 "HELLO"와 "OELLH"라는 두 문자열이 있다고 가정해 보겠습니다. 첫 번째 문자열의 'H'와 'O'의 위치를 서로 바꾸면 "OELLH"가 되어 두 번째 문자열과 정확히 일치합니다. 따라서 이 두 문자열은 메타 문자열입니다.

메타 문자열 판별 알고리즘

두 문자열이 메타 문자열인지 확인하려면 다음 단계를 순서대로 수행합니다.

길이 비교: 두 문자열의 길이가 다르면 즉시 false를 반환합니다.
불일치 문자 탐색: 서로 다른 문자의 개수를 세고, 불일치가 발생한 인덱스를 저장합니다.
개수 검증: 불일치 문자의 개수가 2개를 초과하면 false를 반환합니다. 한 번의 교환으로는 최대 2개의 문자만 고칠 수 있기 때문입니다.
교차 확인: 불일치가 정확히 2개라면, 해당 위치의 문자들이 서로 교차(cross-matched)되는지 확인합니다. 즉, s1[prev] == s2[curr]이고 s1[curr] == s2[prev]를 만족하면 true, 그렇지 않으면 false를 반환합니다.

C++ 구현 코드

#include <iostream>
using namespace std;
bool areTheyMetaString(string s1, string s2) {
    int s1_len = s1.length();
    int s2_len = s2.length();
    if (s1_len != s2_len)
        return false;
    int prev = -1, curr = -1;
    int count = 0;
    for (int i=0; i<s1_len; i++) {
        if (s1[i] != s2[i]) {
            count++; // 불일치 문자 개수 카운트
            if (count > 2)
                return false;
            prev = curr;
            curr = i;
        }
    }
    return (count == 2 && s1[prev] == s2[curr] && s1[curr] == s2[prev]);
}
int main() {
    string s1 = "HELLO", s2 = "OELLH";
    if(areTheyMetaString(s1, s2)){
        cout << "Meta Strings";
    } else {
        cout << "Not Meta Strings";
    }
}

실행 결과

Meta Strings

코드 동작 원리 상세 설명

위 코드의 핵심 로직을 살펴보겠습니다.

길이 검사: s1_len과 s2_len이 다르면 애초에 교환으로 일치시킬 수 없으므로 바로 false를 반환합니다.
불일치 위치 추적: prev와 curr 변수는 각각 이전 불일치 인덱스와 현재 불일치 인덱스를 저장합니다. 반복문을 돌며 문자가 다른 지점을 발견할 때마다 count를 증가시키고, count가 3 이상이 되면 더 이상 볼 필요 없이 false를 반환해 시간을 절약합니다.
최종 판정: 루프가 끝난 후 count가 정확히 2이면서, 두 불일치 위치의 문자들이 서로 교차 일치하는지 검사합니다. 이 조건을 모두 만족해야 한 번의 스왑으로 두 문자열이 같아질 수 있습니다.

이 알고리즘은 문자열 길이에 비례하는 O(n) 시간 복잡도로 동작하며, 추가 메모리 사용 없이 두 개의 인덱스 변수만으로 효율적으로 문제를 해결합니다.