[프로그래머스] 단어 변환 (java)

문제

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java

풀이

1. 처음 시간 초과가 난 코드

import org.junit.jupiter.api.Test;
import java.util.Arrays;
import static org.junit.jupiter.api.Assertions.assertEquals;

class Solution1 {

    static int ans = 51;

    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        if (Arrays.stream(words).anyMatch(x -> x == target)) {
            return 0;
        }

        dfs(words, begin, target, 0);
        return ans == 51? 0: ans;
    }

    public static boolean oneDiff(String a, String b) {
        int cnt = 0;

        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                cnt++;
            }
        }

        return cnt == 1 ? true : false;
    }

    public static void dfs(String[] word, String begin, String target, int cnt) {
        if (begin.equals(target)) { // 대박...
//            System.out.println("check");
            if (cnt < ans) {
//                System.out.println(begin + target);
                ans = cnt;
                return;
            }
        } else if (cnt > word.length) {
            return;
        }

        for (int i = 0; i < word.length; i++) {
            if (oneDiff(begin, word[i])) {
                String[] newWord = new String[word.length - 1];
//                System.out.println(word.length - 1);
                for (int j = 0; j < word.length; j++) {
                    if (j >= i && j !=0) {
//                        System.out.println(i + " " +j);
                        newWord[j - 1] = word[j];
                    } else {
                        newWord[j] = word[j];
                    }
                }

                dfs(word, word[i], target, cnt + 1);
//                System.out.println("begin: " + word[i] + " target: " + target);
            }
        }
    }

    @Test
    public void 정답() {
        String begin = new String("hit");
        String target = new String("cog");
        String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};
        assertEquals(4, solution(begin, target, words));

        begin = "hit";
        target = "cog";
        words = new String[]{"hot", "dot", "dog", "lot", "log"};
        ans = 0;
        assertEquals(0, solution(begin, target, words));

    }

}

2. 정답 코드

class Solution {
    // 아래와 같이 그냥 전역변수 선언해주면 됨
    int ans = 51;
    boolean[] visited;

    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];

        dfs(words, begin, target, 0);

        return ans == 51 ? 0 : ans;
    }

    private void dfs(String[] words, String begin, String target, int cnt) {
        if (begin.equals(target)) {
            ans = ans > cnt ? cnt : ans;
        }


        for (int i = 0; i < words.length; i++) {
            if (!visited[i] && check(begin, words[i])) {
                visited[i] = true;
                dfs(words, words[i], target, cnt + 1);
                // 다음 차례의 dfs는 해당 node를 방문해야함으로!
                visited[i] = false;
            }
        }
    }

    private boolean check(String begin, String word) {
        int cnt = 0;

        for (int i = 0; i < word.length(); i++) {
            if (begin.charAt(i) != word.charAt(i)) {
                cnt++;
            }
        }

        return cnt == 1 ? true : false;
    }
}