C++에서 배열에 한 글자만 다른 문자열이 포함되어 있는지 확인하는 방법

문자열 s와 문자열 배열 A가 주어졌을 때, 배열 안에 현재 문자열과 길이는 같으면서 정확히 한 글자만 다른 문자열이 존재하는지 판별하는 문제입니다.

예를 들어 문자열이 "banana"이고 배열이 ["bana", "orange", "banaba", "banapy"]라고 가정해 보겠습니다. 이때 결과는 true입니다. 배열 속 "banaba"는 "banana"과 길이가 같고 'n' 위치의 한 글자('b' vs 'n')만 다르기 때문입니다.

해결 접근 방법

이 문제는 비교적 단순한 완전 탐색(brute force) 방식으로 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.

배열의 모든 문자열을 순회하면서 각 문자열에 대해 아래 작업을 수행합니다.
- 먼저 배열의 문자열이 s와 길이가 같은지 확인합니다. 길이가 다르면 비교할 필요가 없으므로 건너뜁니다.
- 길이가 같다면 두 문자열을 앞에서부터 한 글자씩 비교하여 불일치 횟수를 셉니다. 불일치가 정확히 한 번이라면 true를 반환하고, 두 번 이상이면 즉시 비교를 중단하고 다음 문자열로 넘어갑니다.
모든 문자열을 검사한 후에도 조건을 만족하는 문자열이 없다면 최종적으로 false를 반환합니다.

예제 코드

#include<iostream>
#include<vector>
using namespace std;
bool hasOneCharMismatch(vector<string>arr, string s) {
    int n = arr.size();
    if (n == 0)
        return false;
    for (int i = 0; i < n; i++) {
        if (arr[i].size() != s.size())
            continue;
        bool difference = false;
        for (int j = 0; j < (int)arr[i].size(); j++) {
            if (arr[i][j] != s[j]) {
                if (!difference)
                    difference = true;
                else {
                    difference = false;
                    break;
                }
            }
        }
        if (difference)
            return true;
    }
    return false;
}
int main() {
    vector<string> arr;
    arr.push_back("bana");
    arr.push_back("orange");
    arr.push_back("banaba");
    arr.push_back("banapy");
    if(hasOneCharMismatch(arr, "banana")){
        cout << "One character mismatch found";
    }
    else{
        cout << "One character mismatch not found";
    }
}

출력 결과

One character mismatch found

코드 동작 원리

hasOneCharMismatch 함수는 배열이 비어 있는 경우 바로 false를 반환합니다. 이후 각 문자열에 대해 길이를 먼저 비교하여 불필요한 연산을 줄이고, 길이가 같은 경우에만 내부 반복문으로 문자를 하나씩 검사합니다.

여기서 핵심은 difference 플래그입니다. 첫 번째 불일치가 발견되면 플래그를 true로 설정하고, 두 번째 불일치가 발견되면 플래그를 false로 되돌린 뒤 반복문을 종료합니다. 따라서 내부 반복문이 끝난 시점에 플래그가 true로 남아 있다면 불일치가 정확히 한 번이었다는 의미이므로 true를 반환하게 됩니다.

시간 복잡도

배열에 n개의 문자열이 있고 각 문자열의 길이가 최대 m이라면, 시간 복잡도는 O(n × m)입니다. 추가 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.