23.03.08 파이썬 코딩 퀴즈#189 단어 변환(프로그래머스 스쿨)

이번 문제는 단어 변환 문제이다.

어떻게 단어가 변환 되는지 부터 살펴보자.

먼저, 한 번에 한 개의 알파벳만 변환되고, words 에 있는 단어로만 변환 가능하다.

입출력 예 1번을 통해 살펴보면, 'hit' 를 'cog' 로 변환해야 하며, 사용가능한 words 는 총 6개가 주어진다.

주어진 조건에 의해 hit이 제일 처음 변환 가능한 words 는 hot 하나이다.

그 다음 hot 에서 변환 가능한 단어는 dot, lot 이다.

dot, lot 에서 변환 가능한 단어는 각 [dog], [log] 이고 두개 다 cog 로 변환 가능하다.

따라서 최소 변환 횟수는 4회가 된다.

 

입출력 예 2번의 경우 words 안에 target 이 존재하지 않기 때문에 변환이 불가능하다. 따라서 0을 반환한다.

별다른 조건은 없고, 한번에 하나의 알파벳만 변환 가능하다는 조건만 염두해 두면 쉬운 문제이다.

먼저 words 에 target 이 존재하지 않는다면, 확인할 필요가 없기 때문에 바로 0을 반환한다.

그렇지 않다면 trans 라는 2차원 배열을 만들어 각 단어들이 변환 가능한 단어들을 저장해 주게 된다.

4중 반복문이지만, 사실 그렇게 반복 횟수는 많지 않다.

먼저 반환 횟수를 결정할 i, 그리고 tran[i]의 단어를 선택할 j, 마지막으로 각 단어들을 알파벳 단위로 끊어서 비교할 k 이다.

한글자가 다를때마다 dif 값이 1씩 증가하며, dif 가 2가 되는 순간 해당 단어와 비교를 종료한다.

그리고 dif 값이 1인 경우라면 변환 가능하기 때문에 해당 단어를 trans[i+1]에 저장해주고, temp 에도 해당 단어를 전달한다. temp 에 한번 사용한 단어를 저장해 줌으로서, 단어가 중복으로 나오는 경우를 막아준다.

그리고 해당 word 가 target 과 같다면, i + 1 값을 반환하고 종료한다.