Daily LeetCode Challenge - 1061. Lexicographically Smallest Equivalent String

Problem From.
https://leetcode.com/problems/lexicographically-smallest-equivalent-string/

오늘 문제는 합집합 찾기로 잘 알려진 Union Find 알고리즘을 사용하여 푸는 문제였다.
(Union Find 를 한눈에 보기 쉽게 잘 설명해준 곳 https://brenden.tistory.com/33)

Union Find 의 개념을 알면 문제를 푸는건 그렇게 어렵지 않았다.
먼저 알파벳 길이만큼의 배열을 선언하고, 각각의 s1 과 s2 의 알파벳을 검사하면서 서로 그룹을 만들어주는데, 사전적으로 더 빠른 순서로 있는 단어를 연결해주면 되었다.
그렇게 만들어진 parent 배열을 활용하여 baseStr 의 알파벳을 하나씩 검사해주며 parent 의 노드안에 있는 문자로 바꿔주면 정답을 얻을 수 있었다.

class Solution {
    fun smallestEquivalentString(s1: String, s2: String, baseStr: String): String {
	    val parent = IntArray(26) { it }
	    for(i in s1.indices){
		    if(s1[i] == s2[i]) continue
		    val x = find(s1[i] - 'a', parent)
		    val y = find(s2[i] - 'a', parent)
		    if(x != y){
			    if(x < y) parent[y] = x
			    else parent[x] = y
		    }
	    }

	    val sb = StringBuilder()
	    for(ch in baseStr) sb.append( 'a' + find(ch - 'a', parent))
	    return sb.toString()
    }
    
    fun find(i: Int, parent: IntArray): Int {
	    if(i == parent[i]) return i
	    return find(parent[i], parent)
    }
}