C++로 두 문자열의 공통되지 않은 문자 찾기

이 튜토리얼에서는 두 문자열에서 공통되지 않은(uncommon) 문자를 찾는 프로그램을 다룹니다.

두 개의 문자열이 주어졌을 때, 어느 한쪽에만 존재하는 문자들을 골라내어 알파벳 순서로 정렬해 출력하는 것이 우리의 과제입니다.

알고리즘 접근 방식

이 문제는 크기 26의 정수 배열을 활용하면 효율적으로 해결할 수 있습니다. 각 인덱스는 알파벳 소문자 하나에 대응되며, 배열 값의 의미는 다음과 같습니다.

• 0: 두 문자열 모두에 해당 문자가 없음
• 1: 첫 번째 문자열에만 해당 문자가 존재함
• 2: 두 번째 문자열에만 해당 문자가 존재함
• -1: 두 문자열 모두에 해당 문자가 존재함 (공통 문자)

먼저 첫 번째 문자열을 순회하며 등장하는 문자의 인덱스 값을 1로 설정합니다. 이후 두 번째 문자열을 순회하면서, 이미 1 또는 -1로 표시된 문자는 -1로 변경하고(두 문자열에 모두 있다는 의미), 처음 등장하는 문자는 2로 설정합니다. 마지막으로 값이 1 또는 2인 인덱스에 해당하는 문자만 출력하면 원하는 결과를 얻을 수 있습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
const int LIMIT_CHAR = 26;

// 공통되지 않은 문자를 찾는 함수
void calculateUncommonCharacters(string str1, string str2) {
    int isthere[LIMIT_CHAR];
    for (int i = 0; i < LIMIT_CHAR; i++)
        isthere[i] = 0;

    int l1 = str1.size();
    int l2 = str2.size();

    // 첫 번째 문자열 처리
    for (int i = 0; i < l1; i++)
        isthere[str1[i] - 'a'] = 1;

    // 두 번째 문자열 처리
    for (int i = 0; i < l2; i++) {
        if (isthere[str2[i] - 'a'] == 1 || isthere[str2[i] - 'a'] == -1)
            isthere[str2[i] - 'a'] = -1;
        else
            isthere[str2[i] - 'a'] = 2;
    }

    // 결과 출력
    for (int i = 0; i < LIMIT_CHAR; i++)
        if (isthere[i] == 1 || isthere[i] == 2)
            cout << (char(i + 'a')) << " ";
}

int main() {
    string str1 = "tutorials";
    string str2 = "point";
    calculateUncommonCharacters(str1, str2);
    return 0;
}

출력 결과

a l n p r s u

결과 분석

"tutorials"에는 t, u, o, r, i, a, l, s가 포함되어 있고, "point"에는 p, o, i, n, t가 포함되어 있습니다. 두 문자열에 공통으로 등장하는 문자는 o, i, t이므로 제외되며, 나머지 문자인 a, l, n, p, r, s, u가 알파벳 순서대로 출력됩니다.

이 방식은 시간 복잡도 O(n + m)(n, m은 각 문자열의 길이)로 동작하며, 추가 메모리는 알파벳 개수에 해당하는 고정 크기 배열 26칸만 사용하므로 매우 효율적입니다.