C++ 유니온 파인드로 풀어보는 스왑 기반 최소 문자열 문제

문자열 s와 인덱스 쌍 배열 pairs가 주어집니다. pairs[i] = [a, b]는 문자열에서 0부터 시작하는 두 인덱스를 의미하며, 우리는 이 쌍에 해당하는 위치의 문자들을 원하는 만큼 몇 번이든 자유롭게 교환할 수 있습니다. 목표는 이러한 교환 연산을 통해 만들 수 있는 문자열 중 사전순으로 가장 작은(lexicographically smallest) 문자열을 찾는 것입니다.

예를 들어 입력이 s = "dcab", pairs = [[0,3], [1,2]]라면 출력은 "bacd"입니다. 먼저 s[0]과 s[3]을 교환하여 s = "bcad"로 만들고, 이어서 s[1]과 s[2]를 교환하면 s = "bacd"가 되기 때문입니다.

해결 전략: 유니온 파인드(Union-Find)

이 문제를 효율적으로 풀려면 유니온 파인드(서로소 집합, Disjoint Set Union) 자료구조를 활용해야 합니다. 서로 교환 가능한 인덱스들은 하나의 연결된 그룹을 형성하고, 같은 그룹에 속한 인덱스들끼리는 문자를 어떤 순서로든 재배치할 수 있습니다. 따라서 각 그룹별로 문자를 정렬한 뒤 다시 조합하면 전체 문자열의 최솟값을 얻을 수 있습니다.

핵심 아이디어는 다음과 같습니다.

교환 가능한 인덱스들을 유니온 파인드로 하나의 그룹으로 묶습니다.
같은 루트(parent)를 공유하는 인덱스들의 문자를 한데 모읍니다.
그룹별로 문자를 내림차순 정렬합니다.
왼쪽 위치부터 차례대로 각 그룹에서 가장 작은 문자를 꺼내 배치하면 사전순 최소 문자열이 완성됩니다.

단계별 알고리즘

n := 문자열의 길이로 설정하고, parent 배열을 크기 n으로 만들어 -1로 초기화합니다.
결과를 담을 문자열 ret을 크기 n으로 만들고 '*'로 채웁니다.
pairs의 각 쌍에 대해 다음을 수행합니다.
- u := pairs[i][0], v := pairs[i][1]
- getParent(u)와 getParent(v)가 같다면 이미 같은 그룹이므로 건너뜁니다.
- 그렇지 않으면 parent[getParent(u)] = getParent(v)로 두 그룹을 병합합니다.
크기 n의 문자 벡터 배열 arr1을 선언합니다.
i = 0부터 n-1까지 각 인덱스의 문자 s[i]를 arr1[getParent(i)]에 추가합니다.
각 arr1[i]를 내림차순으로 정렬합니다. (뒤에서부터 꺼낼 때 가장 작은 문자가 나오도록)
i = 0부터 n-1까지 다음을 반복합니다.
- ret[i] := arr1[getParent(i)]의 마지막 원소
- arr1[getParent(i)].pop_back()으로 마지막 원소를 제거합니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

class Solution {
public:
    vector <int> parent;
    int getParent(int x){
        if(parent[x] == -1) return x;
        return parent[x] = getParent(parent[x]);
    }
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        parent = vector <int>(n, -1);
        string ret(n, '*');
        for(int i = 0; i < pairs.size(); i++){
            int u = pairs[i][0];
            int v = pairs[i][1];
            if(getParent(u) == getParent(v)) continue;
            parent[getParent(u)] = getParent(v);
        }
        vector < char > arr1[n];
        for(int i = 0; i < n; i++){
            arr1[getParent(i)].push_back(s[i]);
        }
        for(int i = 0; i < n; i++){
            sort(arr1[i].rbegin(), arr1[i].rend());
        }
        for(int i = 0; i < n; i++){
            ret[i] = arr1[getParent(i)].back();
            arr1[getParent(i)].pop_back();
        }
        return ret;
    }
};

입력

"dcab"
[[0,3],[1,2]]

출력

"bacd"

동작 원리 정리

getParent 함수는 재귀적으로 루트 노드를 찾으면서 경로 압축(path compression) 기법으로 parent[x]를 직접 갱신하여 이후 탐색 속도를 높입니다. 각 그룹의 문자를 내림차순으로 정렬한 뒤 뒤에서부터 꺼내는 이유는, 왼쪽 위치부터 가장 작은 문자를 우선 배치하기 위함입니다. 이렇게 하면 단일 그룹뿐 아니라 여러 그룹이 섞여 있는 경우에도 전체 문자열이 항상 사전순으로 최소가 됩니다.