C++로 두 문자열에서 고유한 문자 찾기 – 해싱을 활용한 효율적인 방법

이 튜토리얼에서는 주어진 두 문자열에서 고유한(distinct) 문자, 즉 두 문자열 중 하나에만 등장하는 문자를 찾는 방법을 배워보겠습니다. 먼저 예제를 살펴볼까요?

입력

string_one = "tutorialspoint"
string_two = "tutorialsworld"

출력

d n p w

접근 방식: 해싱(Hashing)

이 문제는 중첩 반복문을 사용하는 것보다 맵(map)을 이용한 해싱 기법으로 해결하는 것이 훨씬 효율적입니다. 각 문자의 존재 여부를 O(1) 시간 복잡도로 확인할 수 있기 때문입니다.

문제 해결 단계

두 개의 문자열을 임의의 값으로 초기화합니다.
map<char, int> 타입의 맵 chars를 선언합니다.
첫 번째 문자열을 순회하면서 각 문자를 값 1과 함께 맵에 삽입합니다.
두 번째 문자열을 순회하면서 다음을 수행합니다.
- 현재 문자가 이미 맵에 존재하는지 확인합니다.
- 존재한다면(공통 문자이므로), 해당 문자의 값을 0으로 변경합니다.
- 존재하지 않는다면, 새로운 문자를 값 1과 함께 삽입합니다.
마지막으로 맵을 순회하면서 값이 여전히 1인 문자들만 출력합니다.

예제 코드

아래 코드를 통해 전체 구현 과정을 확인해 보세요.

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

void findDistinctCharacters(string one, string two){
    // 문자열 내 문자 존재 여부를 저장할 맵 초기화
    map<char, int> chars;
    // 첫 번째 문자열 순회
    for (int i = 0; i < one.size(); ++i){
        // 모든 문자를 맵에 삽입
        chars.insert({one[i], 1});
    }
    // 두 번째 문자열 순회
    for (int i = 0; i < two.size(); ++i){
        // 현재 문자가 이미 존재하는지 확인
        if (chars.count(two[i])) {
            // 공통 문자는 값을 0으로 설정
            chars.find(two[i])->second = 0;
        }
        else {
            // 새로운 문자 삽입
            chars.insert({two[i], 1});
        }
    }
    // 고유한 문자 출력
    for (auto item : chars){
        // 값이 1인지 확인
        if (item.second == 1) {
            // 고유한 문자 출력
            cout << item.first << " ";
        }
    }
}

int main(){
    string one = "tutorialspoint";
    string two = "tutorialsworld";
    findDistinctCharacters(one, two);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

d n p w

결과를 보면 't', 'u', 'o', 'r', 'i', 'a', 'l', 's'처럼 두 문자열에 모두 포함된 문자는 제외되고, 오직 한쪽에만 존재하는 문자 'd', 'n', 'p', 'w'만 출력된 것을 확인할 수 있습니다.

마무리

이번 튜토리얼에서는 C++의 map 자료구조를 활용해 두 문자열의 고유한 문자를 찾는 방법을 알아보았습니다. 이 알고리즘의 시간 복잡도는 O(n log n)이며, 중첩 반복문 방식(O(n²))보다 훨씬 빠릅니다. 궁금한 점이 있다면 댓글로 남겨주세요!