프로그래머스 - 단어 변환

lv. 3 단계의 코딩 테스트 연습 문제 중 '단어 변'에 대한 풀이를 설명하고 있습니다.

 

프로그래머스 - 단어 변환

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 조금 어렵게 풀은 감이 있다.
• 일단 최소 변환 수이기 때문에 BFS를 사용했다.
• 어짜피 바꿔야 할 단어와 바뀔 수 있는 단어의 사이즈가 모두 동일하기 때문에, 단어 자리별로 바꿀 수 있는 단어들을 미리 모아놨다.
  • 예를 들어, hit이 있고, [ hot, dot, dog ] 로 바꿀 수 있다면,
  • { 1: [h, d], 2: [o], 3: [t, g] } 이런 식으로 구성했다.
  • 이것은 첫 번째 자리의 단어는 h 혹은 d 로 변경 가능하다는 것을 의미한다.
• 그래서 기준 단어에서 1~n 번째 짜리까지 각 자리에서 바꿀 수 있는 단어로 바꾸고 모두 생성해서 BFS 큐에 넣는다.
  • 위의 예제에 따르면, hit에서 각 자리별로 단어를 하나씩 바꾸면
  • [ dit, hot, hig ] 3개의 단어를 만들 수 있다.
  • 첫 번째 자리에서 h는 현재에서 변함이 없기 때문에 의미가 없고, 세 번째 자리에서 t 역시 현재에서 변함이 없기 때문에 큐에 담지 않는다.
• 그러고 나서 만들어진 단어들은 canMake라는 딕셔너리에 키로 등록한다.
• 한번 만든 단어를 다시 만들 필요가 없기 때문이다.
• 이런 식으로 계속 바꾸면서, target 단어가 만들어지면 그 때의 변경 횟수를 출력하면 된다.
• 단어 변환시 조금 복잡한 코드를 사용했는데,
  • str = "sample" 이 있을 때, 세 번째 자리를 t로 바꾼다고 한다면 str[2] = "t"로 변경할 수가 없다.
  • 문자열이기 때문이다.
  • 그래서 str = list(str) 로 변경한다.
  • 그러면 str = [ 's', 'a', 'm', 'p', 'l', 'e' ] 가 된다.
  • 이 상태에서 str[2] = 't'로 변경이 가능하다.
  • 그러면 str = [ 's', 'a', 't', 'p', 'l', 'e' ] 가 될 것이다.
  • 이 상태에서 "".join(str) 을 이용해서 하나의 문자열로 합쳐주는 식으로 계산을 진행했다.
• 파이썬이 아니었다면,, 문자열 다루다가 죽어버릴 수도 있을 것 같았다...

코드

from collections import deque, defaultdict
def solution(begin, target, words):
    answer = 0
    N = len(target)
    
    q = deque()
    canChange = defaultdict(list)
    for word in words:
        for idx, j in enumerate(word):
            if j not in canChange[idx]:
                canChange[idx].append(j)
    
    q.append([begin, 0])
    
    canMake = {}
    while q:
        data = q.popleft()
        cw = data[0]
        cnt = data[1]

        if cw in canMake:
            continue
        if cw == target:
            answer = cnt
        canMake[cw] = 1
        
        for i in range(N):
            for j in canChange[i]:
                if cw[i] != j:
                    nw = list(cw)
                    nw[i] = j
                    nw = "".join(nw)
                    if nw in words:
                        q.append([nw, cnt + 1])
    return answer

 

탐색은 아이디어를 잘 떠올리기만 하면 쉽게 풀 수 있는 것 같다.

 

추천글

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

프로그래머스