Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 사전순 최소 동치 문자열 찾기 (유니온-파인드)

길이가 같은 두 문자열 A와 B가 주어졌을 때, A[i]와 B[i]는 서로 동치(equivalent)인 문자로 간주합니다. 예를 들어 A = "abc", B = "cde"라면 'a' = 'c', 'b' = 'd', 'c' = 'e'가 성립합니다. 이러한 동치 관계는 다음과 같은 일반적인 동치 관계의 성질을 따릅니다.

  • 반사성(Reflexivity): 'a' = 'a'
  • 대칭성(Symmetry): 'a' = 'b'이면 'b' = 'a'
  • 추이성(Transitivity): 'a' = 'b'이고 'b' = 'c'이면 'a' = 'c'

예를 들어 위의 동치 정보가 주어졌을 때, S = "eed", "acd", "aab"는 모두 서로 동치인 문자열이며, 이 중 "aab"가 사전순으로 가장 작은 동치 문자열입니다. 즉, A와 B로부터 얻은 동치 정보를 활용해 문자열 S를 치환했을 때 만들 수 있는 문자열 중 사전순으로 가장 앞서는 것을 찾는 것이 이 문제의 목표입니다.

입력이 A = "parker", B = "morris", S = "parser"라면 출력은 "makkek"이 됩니다. A와 B의 동치 정보에 따라 문자들을 다음과 같이 그룹으로 묶을 수 있습니다.

[m, p], [a, o], [k, r, s], [e, i]

각 그룹에 속한 문자들은 서로 동치이며, S의 각 위치에서 해당 그룹 내 가장 사전순으로 앞선 문자를 선택하면 답인 "makkek"을 얻을 수 있습니다.

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

이 문제는 유니온-파인드(Union-Find), 즉 서로소 집합(Disjoint Set Union) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 동치인 문자들을 하나의 집합으로 묶고, 각 집합의 대표 문자를 항상 그룹 내에서 가장 작은 문자로 유지하는 것입니다.

알고리즘 단계

  1. 크기 26의 parent 배열을 선언하고 모든 값을 -1로 초기화합니다.
  2. getParent(x): 문자 x의 루트(대표 문자)를 찾습니다. parent[x - 'a']가 -1이면 x 자신이 루트이므로 x - 'a'를 반환하고, 그렇지 않으면 재귀적으로 부모를 따라 올라가며 경로 압축(path compression)을 적용합니다.
  3. union(a, b): 두 문자 a와 b를 같은 집합으로 합칩니다. 각 문자의 루트를 구한 뒤, 더 작은 쪽을 루트로 삼아 사전순으로 가장 작은 문자가 항상 집합의 대표가 되도록 합니다.
  4. A와 B의 각 문자 쌍에 대해 union 연산을 수행합니다.
  5. S의 각 문자에 대해 getParent를 호출한 결과에 'a'를 더해 문자로 변환한 뒤 이어 붙여 최종 문자열을 완성합니다.

다음 구현을 통해 더 잘 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector<int> parent;
    int getParent(char x){
        if(parent[x - 'a'] == -1) return x - 'a';
        return parent[x - 'a'] = getParent('a' + parent[x - 'a']);
    }
    void unionn(char a, char b){
        int parentA = getParent(a);
        int parentB = getParent(b);
        if(parentA == parentB) return;
        if(parentA < parentB){
            parent[parentB] = parentA;
        }else{
            parent[parentA] = parentB;
        }
    }
    string smallestEquivalentString(string A, string B, string S) {
        parent = vector<int>(26, -1);
        for(int i = 0; i < A.size(); i++){
            unionn(A[i], B[i]);
        }
        string ret = "";
        for(int i = 0; i < S.size(); i++){
            ret += getParent(S[i]) + 'a';
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout <<
    (ob.smallestEquivalentString("parker","morris","parser"));
}

입력

"parker"
"morris"
"parser"

출력

makkek

이 구현에서 getParent 함수는 경로 압축을 통해 트리의 깊이를 줄여 탐색 속도를 높이고, union 연산 시 항상 더 작은 문자를 루트로 설정하기 때문에 최종 결과가 자연스럽게 사전순으로 가장 작은 동치 문자열이 됩니다. 전체 시간 복잡도는 문자열 길이에 대해 거의 선형적(O(N))으로 매우 효율적입니다.