[Programmers/JavaScript] Level 3. 단어 변환

 

문제 

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

 

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면

"hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

 

입출력

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

입출력 #1

문제에 나온 예와 같습니다.

 

입출력 #2

target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

제한 사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

 

코드

function solution(begin, target, words) {
    var answer = 0;
    if(words.indexOf(target)==-1) return answer;
    
    var queue = [{word:begin, searched:[]}];
    var result = [];
    while(queue.length!=0) {
        var temp = queue.shift();
        for(var i=0; i<words.length; i++) {
            var tempArr = temp.searched;
            if(tempArr.length>=words.length) continue;
            if(tempArr.length == 0 || tempArr.indexOf(i) == -1) {
                if(checkWord(temp.word, words[i])) {
                    if(words[i] == target) {
                        result.push(tempArr.length+1);
                        continue;
                    }
                    queue.push({word: words[i], searched: [...tempArr, i]});
                }
            }
        }
    }
    if(result.length==0) return answer;
    answer = Math.min(...result);
    
    return answer;
}

function checkWord(myWord, next) {
    var count = 0;
    var copy = next.split('');
    for(var i=0; i<myWord.length; i++) {
        if(copy.indexOf(myWord[i]) != -1) {
            count++;
            copy.splice(copy.indexOf(myWord[i]), 1);
        }
    }
    if(count==myWord.length-1) return true;
}

 

 

설명

이 문제에서 실수했던 2가지에 대해 설명하자면, 

입출력 예시에서 단어 길이가 3인 경우만 생각해서 "한 번에 한 개의 알파벳만 바꿀 수 있습니다." 부분을 간과하고 알파벳이 2개 일치하는지를 체크했다가 틀렸었다.

그래서 (단어의 길이-1)개의 알파벳이 일치하는지를 체크해서 해결했다. 

그렇게 해서 다른 테스트케이스는 다 통과했는데 테스트케이스 3에서 오답이 나왔다.

뭐가 문젠지 모르겠어서 질문하기 게시판에 누군가 올린 테스트케이스3과 관련한 글을 봤더니,

단어에 중복된 알파벳이 있는 경우라는 힌트를 얻게 되었다.

그래서 코드를 수정해서 제출했더니 정답.