C++로 두 문자열 사이의 추가 문자 찾기: 해시 테이블 활용법

두 개의 문자열 S와 T가 있다고 가정해 봅시다. S의 길이는 n이고, T의 길이는 n + 1입니다. 문자열 T에는 S에 포함된 모든 문자가 들어 있으며, 여기에 하나의 추가 문자가 더 포함되어 있습니다. 이번 글에서는 이 추가 문자를 효율적인 방법으로 찾아보겠습니다.

문제 해결 접근 방식

가장 효율적인 방법은 해시 테이블(Hash Table)을 활용하는 것입니다. 알고리즘의 동작 과정은 다음과 같습니다.

먼저 비어 있는 해시 테이블을 하나 생성합니다. 그다음 두 번째 문자열 T의 모든 문자를 해시 테이블에 삽입하면서 각 문자의 등장 횟수를 증가시킵니다. 이후 첫 번째 문자열 S의 각 문자를 순회하며 해당 문자의 카운트를 감소시킵니다. 모든 연산이 끝난 후 카운트 값이 1로 남아 있는 문자가 바로 추가 문자입니다.

이 방식의 시간 복잡도는 O(n)으로, 단순히 모든 문자 쌍을 비교하는 브루트포스 방식(O(n²))보다 훨씬 효율적입니다.

C++ 구현 예제

#include<iostream>
#include<unordered_map>
using namespace std;

char getExtraCharacter(string S, string T) {
    unordered_map<char, int> char_map;
    // 문자열 T의 모든 문자 카운트 증가
    for (int i = 0; i < T.length(); i++)
        char_map[T[i]]++;
    // 문자열 S의 모든 문자 카운트 감소
    for (int i = 0; i < S.length(); i++)
        char_map[S[i]]--;
    // 카운트가 1로 남아 있는 문자가 추가 문자
    for (auto item = char_map.begin(); item != char_map.end(); item++) {
        if (item->second == 1)
            return item->first;
    }
}

int main() {
    string S = "PQRST";
    string T = "TUQPRS";
    cout << "Extra character: " << getExtraCharacter(S, T);
}

실행 결과

Extra character: U

코드 설명

위 예제에서 문자열 S는 "PQRST", 문자열 T는 "TUQPRS"입니다. T에는 S의 모든 문자(P, Q, R, S, T)가 포함되어 있고, 추가 문자로 'U'가 하나 더 들어 있습니다.

unordered_map을 사용하면 각 문자의 등장 횟수를 상수 시간 O(1)에 저장하고 조회할 수 있습니다. T의 문자들을 먼저 삽입한 후 S의 문자들을 제거하면, 최종적으로 'U'만 카운트가 1로 남게 되어 정답을 얻을 수 있습니다.

대안: XOR 비트 연산 활용하기

추가 문자를 찾는 또 다른 우아한 방법은 XOR 연산을 사용하는 것입니다. 같은 값을 XOR하면 0이 되는 성질을 이용하여, 두 문자열의 모든 문자를 순차적으로 XOR하면 최종적으로 추가 문자만 남게 됩니다.

char getExtraCharacterXOR(string S, string T) {
    char result = 0;
    for (char c : S) result ^= c;
    for (char c : T) result ^= c;
    return result;
}

XOR 방식은 추가 메모리 공간이 필요 없어 공간 복잡도가 O(1)이라는 장점이 있습니다.

마무리

두 문자열 사이의 추가 문자를 찾는 문제는 해시 테이블을 사용하면 O(n)의 시간 복잡도로 효율적으로 해결할 수 있으며, 메모리 사용을 최소화하고 싶다면 XOR 비트 연산 기법도 좋은 선택지가 됩니다. 상황에 맞는 적절한 방법을 선택하여 적용해 보시기 바랍니다.