Today's Algorithm(2018-11-20)

programmers 단어 변환

이 문제는 어제부터 시작했었는데요. 테스트 케이스 5개 중 1개가 계속 틀려서 결국 해결하지 못하고 오늘로 넘겼던 문제입니다. 틀린 이유를 여러가지로 생각해봤었는데요. 참 허무하지만 저의 이해의 부족으로 틀렸던 것이더라구요. 그럼 어떤 과정으로 해결해왔는지 간략하게 정리해보겠습니다.

 

맨 처음에는 BFS(너비 우선 탐색)으로 접근하였는데요. 맨 처음 제출하여 틀린 소스코드는 다음과 같습니다.

class Solution {
     public int solution(String begin, String target, String[] words) {
         List<String> wordList = Arrays.asList(words);
         boolean[] visit = new boolean[wordList.size()];
         Queue<Word> queue = new LinkedList<>();
         queue.offer(new Word(begin, 0));

         if(!wordList.contains(target)) return 0;
         while (!queue.isEmpty()) {
             Word word = queue.poll();
             for (int i = 0; i < word.val.length(); i++) {
                 for (char j = 'a'; j <= 'z'; j++) {
                     String temp = word.val.replace(word.val.charAt(i), j);
                     if (temp.equals(target) && wordList.contains(temp)) return word.step + 1;
                     if (wordList.contains(temp) && !visit[wordList.indexOf(temp)]) {
                         queue.offer(new Word(temp, word.step + 1));
                         visit[wordList.indexOf(temp)] = true;
                     }
                 }
             }
         }
         return 0;  
     }
 }

 class Word {
     String val;
     int step;

     public Word(String val, int step) {
         this.val = val;
         this.step = step;
     }
 } 

이 소스코드의 문제는 무엇이었을까요? 제가 생각했던 문제는 visit배열이 제대로 작동하지 않는다는 것입니다. 원래 각각의 경우에 대해서 visit배열이 표시되어야 하는데 저는 모든 경우에 대해 visit배열 하나로만 표시하고 있었기 때문에 제대로 작동하지 않았던 것입니다. 하지만 나중에 알게된 것은 이것만의 잘못은 아니더라구요!

 

이후에 BFS로는 다른 방법이 떠오르지 않아 DFS로 다시 접근하였습니다. 그런데 이 또한 똑같은 테스트 케이스 번호에서 막혔는데요. 구글링하면서 저랑 똑같은 고민을 하고 있는 다른 분들을 찾아봤지만 없었습니다. 그리곤 제가 다음과 같은 테스트 케이스를 만들고 나서 테스트하고 있는데 제가 생각하지 않은 답이 나오지 않은 것을 보고 뭔가 다른 곳에서 잘못 돌아가고 있다는 것을 알게되었습니다.

    @Test
    public void test3() {
        String begin = "aaaa";
        String target = "bbbb";
        String[] words = {"aaab", "aabb", "abbb", "bbbb"};

        assertThat(problem.solution(begin, target, words)).isEqualTo(4);
    }

여기서 1이 나왔는데요. System.out.println() 출력을 통해 문제점은 String temp = word.val.replace(word.val.charAt(i), j); 부분인 것을 알게되었습니다. replace()메서드가 해당 index의 char을 바꿔주는 것이 아닌 문자열 내 해당 char 모두를 j로 바꿔주는 것이었습니다. 그래서 구글링하여 찾아보니 String은 immutable이기 때문에 불가능하고 StringBuilder 을 이용해야 함을 알 수 있었습니다. 다음과 같이요.

        StringBuilder sb = new StringBuilder(word.val);
        sb.setCharAt(i, j);
        String temp = sb.toString();

StringBuilder 생성자를 통해 객체를 만들어주고 setCharAt() 메서드를 통해 바꾸는 것입니다. 이번엔 제대로 된 확인을 통해 제가 원하던 특정 인덱스의 char이 바뀌는 것을 확인할 수 있었습니다. 이를 이용하여 DFS를 풀면 다음과 같습니다.

class Solution2 {
    List<String> wordList;
    boolean[] visit;
    int answer;

    public int solution(String begin, String target, String[] words) {
        wordList = Arrays.asList(words);
        visit = new boolean[wordList.size()];
        answer = words.length + 1;

        dfs(new Word(begin, 0), target);
        if(answer == words.length + 1) return 0;
        return answer;
    }

     void dfs(Word word, String target) {
        for (int i = 0; i < word.val.length(); i++) {
            for (char j = 'a'; j <= 'z'; j++) {
                StringBuilder sb = new StringBuilder(word.val);
                sb.setCharAt(i, j);
                String temp = sb.toString();
                if(temp.equals(word.val)) continue;
                if(temp.equals(target) && wordList.contains(temp)) {
                    answer = Math.min(answer, word.step + 1);
                }
                if (wordList.contains(temp) && !visit[wordList.indexOf(temp)]) {
                    visit[wordList.indexOf(temp)] = true;
                    dfs(new Word(temp, word.step + 1), target);
                    visit[wordList.indexOf(temp)] = false;
                }
            }
        }
    }
}

class Word {
    String val;
    int step;

    public Word(String val, int step) {
        this.val = val;
        this.step = step;
    }
}

29줄을 통해 기존 DFS에서 각각의 경우의 수에 대해 visit배열의 독립성을 지키지 못하던 것을 해결할 수 있었습니다. 이렇게 하여 문제를 해결하고 나서 이전 DFS 접근법에서 replace() 대신 StringBuilder 의 setCharAt() 로 바꿔어 보았는데요. visit배열의 독립성 문제를 해결하지 못했는데도 불구하고 통과되더라구요. 아마도 테스트 케이스가 5개 밖에 안되는데 그렇다보니 제대로 검증이 안된 것 같아요.

 

생각지도 못한던 부분에서 오류가 나타나 찾기가 힘들었네요! 다음에 문제가 틀릴 때도 제가 생각하지 못하던 부분도 틀릴 수 있다는 생각으로 접근해야할 것 같습니다.