본문으로 건너뛰기

1061 - Lexicographically Smallest Equivalent String

info

풀이 키워드​

스포주의

유니온파인드


풀이 코드​

info
  • 메모리: 41850 KB
  • 시간: 2 ms
class Solution {
    int[] nxt;
    
    public void union(int a, int b) {
        int r1 = find(a);
        int r2 = find(b);
        
        if (r1 < r2) nxt[r2] = r1;
        else if (r1 > r2) nxt[r1] = r2;
        else return;
    }

    public int find(int n) {
        if (n == nxt[n]) return n; // is root
        int root = find(nxt[n]);
        nxt[n] = root;
        return root;
    }

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        nxt = new int[26];
        for (int i = 0; i < 26; ++i) nxt[i] = i;

        // guarantee lex smallest by root value comparison
        // ex. if r1 < r2 then nxt[r2] = r1

        char[] s1Arr = s1.toCharArray();
        char[] s2Arr = s2.toCharArray();
        for (int i = 0; i < s1.length(); ++i) {
            int a = s1Arr[i]-'a';
            int b = s2Arr[i]-'a';
            if (find(a) != find(b)) union(a, b);
        }

        StringBuilder sb = new StringBuilder();
        for (char ch : baseStr.toCharArray()) {
            sb.append((char)(find(ch-'a')+'a'));
        }

        return sb.toString();
    }
}

풀이 해설​

유니온파인드 알고리즘을 통해 문자를 집합으로 묶고, 각 집합 내 lexicographically smallest한 문자를 알아내서

baseStr을 해당 문자로 치환해야 하는 문제이다.

lex smallest는 union하는 과정으로부터 자연스럽게 도출되므로, 대놓고 유니온파인드 문제임을 알 수 있다.
(lex largest는 union 로직에서 if r1 < r2 then nxt[r1] = r2처럼 condition을 조정하면 된다.)


🐳 Union-Find 이해하기​

지난번 백준 1717번에서 그린 diagram은 약간 아쉬운 예시를 들었기에, 다시 설명해보겠다.


뭘 어떻게 구현했더라?​

기억이 잘 안난다면 정상이다. 애초에 유니온파인드에서 사용되는 parent라는 네이밍부터 뭔가 잘 안와닿았다.

일정 시간 원리를 이해하는 과정 끝에 필자는 해당 네이밍을 next라고 하겠다. (코드 상으론 nxt)

CS 이론 중 연결리스트를 잘 공부했다면, 이 next를 가지고 뭘 해야 할지 잘 연상이 될 것이다.

"어... 다음 노드로 넘어가야겠는데?"

그렇다. 이렇게 재귀적으로 다음 다음 다음 넘겨서 최종적으로 더이상 다음 노드로 가지 못할때까지,
다시 말해 종점 노드(=루트)까지 순회해서 루트 노드를 알아내는 것이 find 함수이다.

그렇다면 union 함수는 무엇일까?

union은 find로 알아낸 루트 노드끼리 값을 비교해서, 둘이 다르다면 정해진 조건에 따라 값을 한쪽으로 통일해주는 역할을 한다. 그리고 그 '정해진 조건'이라는 것은 더 작은 값을 기준으로 하든,

if (r1 < r2) nxt[r2] = r1; // 더 작은 r1으로 통일
else if (r1 > r2) nxt[r1] = r2; // 더 작은 r2로 통일

아니면 더 큰 값을 기준으로 하든,

if (r1 < r2) nxt[r1] = r2; // 더 큰 r2로 통일
else if (r1 > r2) nxt[r2] = r1; // 더 큰 r1으로 통일

문제에 맞게끔 융통성을 발휘하면 된다. 참고로 이 문제에선 lex smallest를 구해야 하므로 더 작은 값으로 통일하고 있다.


뭐가 어떻게 돌아가는건데​

다음의 두 그룹이 있다.

{a, b} 그룹: a(0)가 루트
{c, d} 그룹: c(2)가 루트

여기서 a,b,c,d는 일종의 닉네임, 그리고 닉넴-'a' 연산으로 도출되는 0,1,2,3은 실명이라고 하자.
그룹을 대표하는 루트는 실명값이 가장 작은 사람이 맡기로 했으므로, next 배열은 이런 상태이다.

next 배열
name : [0] [1] [2] [3]
next : {0,  0,  2,  2}

b(1): "제가 속한 그룹의 루트는 a(0)에요"
d(3): "제가 속한 그룹의 루트는 c(2)에요"


char[] s1Arr = s1.toCharArray();
char[] s2Arr = s2.toCharArray();
for (int i = 0; i < s1.length(); ++i) {
    int a = s1Arr[i]-'a';
    int b = s2Arr[i]-'a';
    if (find(a) != find(b)) union(a, b);
}

그런데 이런 그룹핑 상태에서, {b, c}가 같은 그룹이라는 새로운 사실이 발견된다.

이전까지는 서로 다른 그룹으로 알았었기에, b와 c는 곧장 union을 실행했다.

public void union(int a, int b) {
    int r1 = find(a); // 1
    int r2 = find(b); // 1
    
    if (r1 < r2) nxt[r2] = r1; // 2
    else if (r1 > r2) nxt[r1] = r2;
    else return;
}
  1. b와 c가 속한 그룹의 루트를 구하니 각각 a(0), c(2)가 나왔다.
  2. a(0) < c(2) 이므로, c의 next가 a로 변경되었다.
next 배열
name : [0] [1] [2] [3]
next : {0,  0,  2,  2}

즉, 기존 next 배열이 이런 상태에서

next 배열
name : [0] [1] [2] [3]
next : {0,  0,  0,  2}

상단의 상태로 수정된다.

이처럼 union은 그냥 루트끼리 next를 수정해주는 작업이다. 정말 루트 것만 수정해준다.


그럼 루트 아닌 애들은요??

언뜻 보면 d가 혼자 2라서 그룹핑으로부터 누락된 것처럼 보이지만, 저 배열의 이름이 뭐였더라? next이다.

d의 2값은 d의 다음 노드 번호일 뿐, d의 그룹 번호가 아니라서 괜찮다.


public int find(int n) { // find: "님 루트임?"
    if (n == nxt[n]) return n; // n: "넹"
    int root = find(nxt[n]); // n: "아녀 nxt[n]일걸요?"
    nxt[n] = root; // find: "님 루트 root던데"
    return root;
}

정 못믿겠다면 find로 d(3)의 그룹을 찾아보자.

find는 재귀함수이고, 루트를 찾을때까지 next로 이동하며 재귀한다. 루트의 판별 조건은 next가 자기 자신일 때이다.

다시 말해, 더이상 이동할 next가 없어 종점에 다다른 경우이다.

find 과정
find(3)

find(3)을 호출했더니, next[3]=2 가 나왔다. 이 말인 즉슨 d(3)가 "나 루트 아님 c(2)로 가보셈" 한 것이다.

find 과정
find(3) -> find(2)

그러니 재귀 호출로 find(2)를 호출해서 c(2)로 가본다. next[2]=0 이므로 여전히 루트가 아니고 0으로 가야 한다.

find 과정
find(3) -> find(2) -> find(0)

find(0)을 호출한다. next[0]=0이니 아하 a(0)가 루트였구나! 그럼 이제 루트 알았으니 돌아가자...

돌아갈땐 여기까지 온 순서의 역순으로 가는데, 그냥 가는거 아니고 왔던 길목의 next 값을 업데이트해주면서 간다.

돌아갈 겸 경로 압축도 같이 하는 것이다.

find 과정
find(3) <- find(2) <- (반환됨)

next[2] = 0; "c(2)야 다음번에 누가 next 물어보면 a(0)로 가라고 해"

find 과정
find(3) <- (반환됨) <- (반환됨)

next[3] = 0; "d(3)야 다음번에 누가 next 물어보면 a(0)로 가라고 해"

next 배열
name : [0] [1] [2] [3]
next : {0,  0,  0,  0}

그래서 find(3) 한번 수행한 직후에는 next[3]이 루트임이 보장된다.

갈땐 건너건너 삽질하면서 루트에 도달했지만, 올때 업뎃했기 때문이다. 다음번엔 좀 더 빨리 루트에 도달할 수 있을 것이다.

다만 find 호출 이후 union 작업이 있었다면 어디서 또 next 수정 작업이 일어났는지 모르니까

그냥 딱 다음 노드 정도의 의미만 갖는 것이지, next가 곧 루트라는 것은 보장하지 못한다.


next는 이것만 보장한다.

"저는 다음 정류장밖에 모르는데...어쨌든 종점은 루트니까 가보세여"


정리하자면,​

  • union: 두 그룹의 루트 중에서 하나를 골라 루트 자격 박탈하기(next 수정)
  • find: 건너건너 이동하며 삽질을 통해 루트 알아내기
    • 돌아오는 길에 루트 정보를 업뎃(=경로 압축)해서 다음번엔 덜 삽질하도록 함

메모​

  • 이제 좀 유니온파인드가 기억에 남을듯