뒤죽박죽 코딩 이야기

2023년 01월 14일 토요일 - 헤롱헤롱

오늘 올려볼 문제는 1061번 Lexicographically Smallest Equivalent String 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

어으 낮부터 술을 좀 마셨더니 머리가 아프구만

입력

사진에서도 볼 수 있듯이 String 3개가 입력으로 들어온다.

풀이 및 코드

s1과 s2의 각 원소들끼리 대치가 가능하다고 한다.

abc와 def가 있다고 하면 a는 d랑 동일한 그룹에 포함되고 이 그룹안에서는 어떤 것이든 동등하다고 한다.

이렇게 그룹이 있다고 했을 때 baseStr을 사전적으로 가장 빠른 순서가 되게끔 바꾸어 구하는 것이 이 문제다.

조금 헤매다가 정답을 생각해냈다.

결국에 그룹을 만든다고 생각하면 Union Find를 사용하는게 가장 편했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    int[] arr = new int[26];
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        for(int i = 0; i < arr.length; i++) arr[i] = i;
        
        for(int i = 0; i < s1.length(); i++) {
            int c1 = find(s1.charAt(i) - 'a'), c2 = find(s2.charAt(i) - 'a');
            
            if(c1 == c2) continue;
            
            arr[Math.max(c1, c2)] = Math.min(c1, c2);
        }
        
        var sb = new StringBuilder();
        for(var c : baseStr.toCharArray()) sb.append((char)('a' + find(c - 'a')));
        
        return sb.toString();
    }
    
    public int find(int num) {
        if(arr[num] == num) return num;
        else return  arr[num] = find(arr[num]);
    }
}

제출 화면

어우 뭔가 오랜만에 블로그를 쓰는 것 같은데 그건 제 실력이 모자라서입니다...

최근 문제들이 다 어려웠어잉..

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.