[파이썬/프로그래머스]단어 변환

링크: https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

문제:

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

 

[규칙]

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.

2. words에 있는 단어로만 변환할 수 있습니다.

 

 

코드:

def diff(str1, str2):
    res = 0
    for i in range(len(str1)):
        if str1[i] != str2[i]:
            res += 1
    return res

def solution(begin, target, words):
    cnt= 0
    
    if target not in words:
        return 0
    
    while begin != target:
        replace = [word for word in words if diff(begin, word) == 1]
        if not replace and begin != target:
            return 0
        if len(replace)>1:
            replace.sort(key=lambda x: diff(begin, x))
            
        begin = replace[-1]
        words.remove(begin)
        cnt += 1
    return cnt

 

쉽게 생각하면 쉽게 풀리는 문제다.

 

1. 우선 규칙 1번에 따라 words에 있는 단어 중 한 개의 알파벳만 다른 단어를 찾는다. -> replace: List[str]

2. 아직 begin과 target이 같지 않은데 바꿀 수 있는 단어가 없다면 변환할 수 없는 경우다.

3. 바꿀 수 있는 단어가 1개 이상이라면, 정답과 가장 가까운(개수 차이가 가장 적은) 단어를 찾는다. -> replace를 거리가 먼 순으로 정렬

4. begin은 바꿀 수 있는 단어 중 정답과 가장 가까운 단어 -> replace[-1]

5. 한번 바꾼 건 다시 사용하지 않으니까 words에서 제거 -> words.remove(begin)

6. 단계 하나 증가 -> cnt += 1

 

문제에서 '최소 몇 단계의 과정을 거쳐'라고 해서 BFS로 구현해야 할 거같아서 고민하다가, 우선 떠오르는 쉬운 풀이를 해보고 안되면 구현하려고 했는데 다행히 한번에 통과했다.