C++ 유니온-파인드로 풀어보는 유사한 문자열 그룹 문제

문제 이해하기

두 문자열 X와 Y가 있을 때, X의 두 글자를 서로 바꿔서 Y와 동일하게 만들 수 있다면 두 문자열은 "유사(similar)"하다고 정의합니다. 또한 두 문자열이 처음부터 완전히 같은 경우에도 유사하다고 간주합니다.

예를 들어 "tars"와 "rats"는 t와 r을 맞바꾸면 서로 같아지므로 유사합니다. 마찬가지로 "rats"와 "arts"도 유사하지만, "star"는 "tars", "rats", "arts" 어느 것과도 유사하지 않습니다. 따라서 이 문자열들은 {"tars", "rats", "arts"}와 {"star"}라는 두 개의 연결된 그룹을 형성합니다.

흥미로운 점은 "tars"와 "arts"가 직접적으로 유사하지 않음에도 불구하고 같은 그룹에 속한다는 것입니다. 즉, 어떤 단어가 특정 그룹에 속한다는 것은 해당 그룹 내 최소 한 개의 다른 단어와 유사함을 의미합니다.

문자열 배열 A가 주어졌을 때, A의 모든 문자열은 서로 애너그램(anagram) 관계입니다. 이때 총 몇 개의 그룹이 만들어지는지 구하는 것이 이 문제의 목표입니다.

입력이 ["tars", "rats", "arts", "star"]라면 출력은 2가 됩니다.

접근 방법: 유니온-파인드(Union-Find)

이 문제는 유니온-파인드, 즉 분리 집합(Disjoint Set Union) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 기본 아이디어는 다음과 같습니다.

처음에는 모든 문자열이 각자 독립적인 그룹에 속한다고 가정합니다.
두 문자열이 유사한지 검사하여, 유사하다면 두 문자열을 같은 그룹으로 합칩니다(union).
실제로 그룹이 병합될 때마다 전체 그룹의 개수를 하나씩 줄입니다.

알고리즘 단계

parent 배열과 rank 배열을 정의합니다. parent는 각 노드의 부모를, rank는 집합의 크기를 추적합니다.

getParent(x) 함수:

parent[x]가 -1이면 x가 루트이므로 x를 반환합니다.
그렇지 않으면 경로 압축(path compression)을 적용하며 재귀적으로 루트를 찾습니다: parent[x] = getParent(parent[x])

unionn(x, y) 함수:

parX := getParent(x), parY := getParent(y)
parX와 parY가 같으면 이미 같은 그룹이므로 false를 반환합니다.
rank[parX] >= rank[parY]이면 parY를 parX 아래에 붙이고 rank[parX]에 rank[parY]를 더합니다.
그렇지 않으면 parX를 parY 아래에 붙이고 rank[parY]에 rank[parX]를 더합니다.
병합에 성공했으므로 true를 반환합니다.

ok(s1, s2) 함수 — 유사 여부 판단:

cnt := 0으로 초기화합니다.
s1의 각 위치를 순회하면서 s1[i]와 s2[i]가 다르면 cnt를 1씩 증가시킵니다.
cnt가 2를 초과하면 false를 반환합니다(두 글자 교환으로는 3개 이상의 차이를 메울 수 없기 때문입니다).
순회가 끝나면 true를 반환합니다.

메인 로직(numSimilarGroups):

n := A의 크기, ret := n으로 초기화합니다.
parent 배열을 n개 크기로 만들고 -1로 채웁니다.
rank 배열을 n개 크기로 만들고 1로 채웁니다.
모든 문자열 쌍 (i, j)에 대해 ok(A[i], A[j])가 참이면 unionn(i, j)를 호출하고, 병합에 성공하면 ret을 1 감소시킵니다.
최종적으로 ret을 반환합니다.

C++ 구현 예제

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

class Solution {
   public:
   vector<int> parent;
   vector<int> rank;

   int getParent(int x){
      if (parent[x] == -1)
      return x;
      return parent[x] = getParent(parent[x]);
   }

   bool unionn(int x, int y){
      int parX = getParent(x);
      int parY = getParent(y);
      if (parX == parY)
      return false;
      if (rank[parX] >= rank[parY]) {
         rank[parX] += rank[parY];
         parent[parY] = parX;
      } else {
         rank[parY] += rank[parX];
         parent[parX] = parY;
      }
      return true;
   }

   bool ok(string& s1, string& s2){
      int cnt = 0;
      for (int i = 0; i < s1.size(); i++) {
         if (s1[i] != s2[i])
         cnt++;
         if (cnt > 2)
         return false;
      }
      return true;
   }

   int numSimilarGroups(vector<string>& A){
      int ret = 0;
      int n = A.size();
      ret = n;
      parent = vector<int>(n, -1);
      rank = vector<int>(n, 1);
      for (int i = 0; i < n; i++) {
         for (int j = i + 1; j < n; j++) {
            if (ok(A[i], A[j])) {
               if (unionn(i, j))
               ret--;
            }
         }
      }
      return ret;
   }
};

main(){
   Solution ob;
   vector<string> v = {"tars","rats","arts","star"};
   cout << (ob.numSimilarGroups(v));
}

입력

{"tars","rats","arts","star"}

출력

복잡도 분석 및 핵심 포인트

모든 문자열 쌍을 비교해야 하므로 시간 복잡도는 O(N² × L)입니다(N은 문자열 개수, L은 문자열 길이). 다만 유니온-파인드에 경로 압축과 랭크 기반 병합을 적용했기 때문에 집합 연산 자체는 거의 상수 시간에 처리됩니다.

핵심은 "두 글자만 다른 경우에만 유사"라는 조건을 ok() 함수에서 정확히 구현하는 것입니다. 모든 입력 문자열이 서로 애너그램이라는 보장이 있으므로, 다른 위치의 개수가 정확히 2개라면 반드시 한 번의 교환으로 일치시킬 수 있습니다.