[LeetCode 1061] Lexicographically Smallest Equivalent String

1061. Lexicographically Smallest Equivalent String

📌 문제 개념

주어진 두 개의 문자열 s1과 s2는 같은 길이를 가지며, 각 인덱스에 해당하는 문자들은 서로 동등한 관계를 가진다.

이때, 동등 관계에 대한 성질은:
1. Reflexivity: 'a' == 'a'
2. Symmetry: 'a' == 'b' 이면, 'b' == 'a'
3. Transitivity: 'a' == 'b'이고, 'b' == 'c'이면, 'a' == 'c'

세 성질을 만족한다.

결국 구하고자 하는 것은 입력으로 주어진 baseStr을 동등 관계를 사용해서 변환할 수 있는 가장 작은 문자열로 바꾸는 것이다.

제약사항

• s1.length == s2.length <= 1000
• baseStr.length <= 1000
• s1, s2, baseStr는 모두 소문자로만 이루어짐.

📌 접근 방식

• 1000개의 노드만 관리하면 되므로, Union-Find를 활용하여 풀이가 가능하다.
• 동등한 위치에 존재하는 s1, s2의 각 문자를 동일한 집합에 Union하게 된다면, 자연스럽게 위의 3가지 성질을 만족할 것이다. 그 이유는,

1. Reflexivity: 기본적으로 parent[x] = x로 초기화 되어 있다. 즉, 'a' == 'a'일때, find(a) = a이다.
2. Symmetry: 'a' == 'b'일때, a와 b는 같은 집합으로 묶이면서 find(a)와 find(b)는 같은 값을 가진다.
3. Transitivity: 'a' == 'b', 'b' == 'c'일때, a,b,c는 모두 같은 집합으로 묶이면서, find(a), find(b), find(c)는 모두 같은 값을 가진다.

📌 풀이 설명

• union-find를 사용하기 전, 각 문자를 int로 치환하는 과정이 필요하다.

  • (int)s1[i] - (int)'a' (0~25로 문자를 치환)

• 이제 s1과 s2 문자열 중 같은 index에 위치한 문자를 union한다.

  • union과정 중에 더 작은 문자가 parent로 지정될 수 있도록 해준다.

         if(y < x){
            parent[x] = y;
        } else {
            parent[y] = x;
        }

• 후에, bastStr을 순회하면서, baseStr 문자를 find한 값으로 바꾸어 준다.

📌 정답

class Solution {
public:
    int parent[26];

    int find(int x){
        if(parent[x] == x){
            return x;
        }

        return parent[x] = find(parent[x]);
    }

    void merge(int x, int y){
        x = find(x);
        y = find(y);
		
        // 더 작은 것을 parent로 만드는 과정
        if(y < x){
            parent[x] = y;
        } else {
            parent[y] = x;
        }
    }

    string smallestEquivalentString(string s1, string s2, string baseStr) {

        for(int i= 0 ;  i<26; i++){
            parent[i] = i;
        }

        for(int i = 0 ; i<s1.size(); i++){
            int index = (int)s1[i] - (int)'a';
            int index2 = (int)s2[i] - (int)'a';
            merge(index, index2);
        }

        string answer = "";
        
        for(int i = 0 ; i< baseStr.size(); i++){
            int index = (int)baseStr[i] - (int)'a';
            int value = find(index);
            answer += (char)(value + (int)'a');
        }

        return answer;
    }
};