C++로 두 문자열에서 공통되지 않은 문자 찾는 방법

개요

이 글에서는 서로 다른 두 문자열을 비교했을 때 공통되지 않은(uncommon) 문자를 찾아내는 C++ 프로그램을 살펴보겠습니다.

문자열은 본질적으로 문자(character)들의 배열입니다. 따라서 비교를 수행하려면 한 문자열의 각 문자를 순회하면서, 그 문자가 다른 문자열에도 존재하는지 동시에 확인하면 됩니다.

첫 번째 문자열을 A, 두 번째 문자열을 B라고 가정해 보겠습니다. 이때 A에는 있지만 B에는 없는 문자들의 집합은 A − B로 표현할 수 있으며, 같은 방식으로 B − A도 구할 수 있습니다.

이 두 결과를 합치면 다음과 같습니다.

( A - B ) ∪ ( B - A )

즉, 두 문자열 전체에서 공통되지 않은 문자들이 됩니다.

예제 코드

#include <iostream>
using namespace std;
int main() {
   int len1 = 5, len2 = 4;
   char str1[len1] = "afbde", str2[len2] = "wabq";
   cout << "Uncommon Elements :" <<endl;
   //str1 - str2를 계산하는 루프
   for(int i = 0; i < len1; i++) {
      for(int j = 0; j < len2; j++) {
         if(str1[i] == str2[j])
            break;
         //문자열의 끝에 도달한 경우
         else if(j == len2-1) {
            cout << str1[i] << endl;
            break;
         }
      }
   }
   //str2 - str1을 계산하는 루프
   for(int i = 0; i < len2; i++) {
      for(int j = 0; j < len1; j++) {
         if(str2[i] == str1[j])
            break;
         else if(j == len1-1) {
            cout << str2[i] << endl;
            break;
         }
      }
   }
   return 0;
}

실행 결과

Uncommon Elements :
f
d
e
w
q

동작 원리 및 시간 복잡도

위 코드는 중첩 반복문(nested loop)을 사용합니다. 바깥쪽 반복문은 한 문자열의 각 문자를 차례대로 확인하고, 안쪽 반복문은 해당 문자가 다른 문자열에 존재하는지 검사합니다. 일치하는 문자를 발견하면 break로 내부 루프를 즉시 빠져나가며, 끝까지 일치하는 문자가 없다면 그 문자는 공통되지 않은 문자이므로 화면에 출력합니다.

이 접근 방식의 시간 복잡도는 O(n × m)입니다. 여기서 n과 m은 각각 두 문자열의 길이입니다. 문자열의 길이가 매우 긴 경우에는 set이나 unordered_set 같은 해시 기반 자료구조를 활용하면 시간 복잡도를 O(n + m)으로 개선할 수 있습니다.