두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- 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 안에 없기 때문에 변환할 수 없습니다.
function solution(begin, target, words) { if(!words.includes(target)) return 0; const process = [begin]; // 변환 과정 담는 배열 let idx = 0; // words에서 사용할 index while(!process.includes(target)) { if(differenceCheck(begin, target, process)) { begin = target; process.push(begin); } if(differenceCheck(begin, words[idx], process)) { begin = words[idx]; process.push(begin); } if(idx < words.length - 1) { idx++; } else { idx = 0; } } return process.length - 1; } // 다른 알파벳 개수 확인하는 함수 function differenceCheck(str1, str2, arr) { const length = str1.length; let difference = 0; for(let i = 0; i < length; i++) { if(str1[i] !== str2[i]) { difference++; } if(difference > 1) break; } if(difference === 1 && !arr.includes(str2)) { return true; } else { return false; } }
단어에서 알파벳 하나씩 바꿔가면서
target
을 만들 수 있느냐를 찾아야되는데우선 단어에서 알파벳 다른 개수를 찾기위한 함수
differenceCheck
를 만듦.그렇게 찾아진 단어를
process
배열에 담는다.반복문을 계속 돌리면서 현재까지 변환된 단어가
target
이랑 하나 차이나는지 먼저 확인하고 아니면words
에서 하나 차이나는 단어를 찾는다.그렇게
target
을 찾을 때 까지 계속 반복.랜덤하게 위치가 섞여있었으면 로직에 추가되야 할 게 더 있지만 일단 저렇게 해도 통과되는걸 보니 아마 변환되는 과정의 단어들이 순차적으로 들어있는거 같음.
일단 이 로직은 현재 문제에서는 통과가 되지만 미완성 로직이라고 볼 수 있음.