[프로그래머스] 단어 변환

오늘은 어제보다 덜 덥고 날씨가 너무 좋다 놀러 가고 싶다🦍

 

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

 

문제에 사연이 없으니까 재미가 없다. 사연이 있어야 재밌다 예를 들면 가은이가 친구들과 게임을 하며 단어를 배우려고 한다. 단어의 스펠링 하나씩만 바꿔 단어를 만드는 사람이 이긴다. 이럴 때 가은이가 게임에서 이기는 방법을 알려주자! 이러면 재밌는데... 문제가 너무 딱딱하다... 그래도 함수를 작성해주자!!🥰

 

문제 설명

두 개의 단어 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 함수를 작성해주세요.

 

제한사항

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

해당 문제는 입출력 예만 보면 바로 이해가 가능하다.

입출력 예

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

hit -> hot -> dot -> dog ->cog

hit -> hot -> dot -> dog -> log -> cog

hit -> hot -> lot ->dot -> dog -> cog

hit -> hot -> lot ->log ->cog

hit -> hot -> lot ->log ->dog -> cog

이런 식으로 엄청 많은 루틴 중에 가장 최솟값으로 begin ->target까지 도착하는 것을 고르면 된다.

 

 

풀이 방법

words의 배열의 단어를 하나하나씩 begin과 비교하여 한 글자만 다른 걸 찾고, 조건과 적합한 단어를 찾으면 카피한 copy_words배열에 그 단어를 빼고 단어는 begin으로 변환한 뒤 재귀를 계속 도는 과정을 통해 begin과 target과 맞는지 확인하는 과정을 거쳤다. 

 

왜?

입출력 예와 제한사항을 보면 알겠지만 문제에서는 중요한 3가지가 있다.

 변환 과정이 제일 적은 값을 구한다는 것, 변환이 불가능한 경우에는 0을 return 한다는 것 그리고 범위가 생각보다 엄청 좁다는 것이다.

그래서 이 문제는 하나하나 꼼꼼히 탐색하면서 알아보는 게 좋다고 생각해서 이러한 풀이를 적용했다.

 

여기서 중요한 게 범위가 크다면 재귀를 돌릴 수 있을지도 모르고 만약 돌린다면

sys를 import 하고 sys.setrecursionlimit(10000) 추가해주는 게 좋음.

 

코드

import copy
global num
num=987654321
#그리고 중요한게 여기서는 범위가 되게 좁기 때문에 그냥 돌았지만
#만약 범위가 크다면 재귀를 돌릴 수 있을지 모르고
#돌린다면 import sys sys.setrecursionlimit(10000) 추가해주는게 좋음.
def solution(begin, target, words):
    answer = 0
    recursion(begin,target,words,0)
    if num==987654321:#한번도 begin==target인 부분이 없을때는 return 0
        return 0
    else:
        return num#한번이라도 매칭되는 부분이 있으면 min에 의거해서 num을 return
    
def recursion(begin,target,words,count):
    global num
    print(words)
    if begin==target:#돌다가 begin이랑 target이랑 같을 때
        num=min(num,count)#가장 최소값을 구하는 것이니 min 내장함수로 이전 값하고 비교.
        return 0
    
    for i in range(len(words)):#이거 단어를 도는 거고
        standard=0
        for j in range(len(begin)):#스펠링하나하나를 비교하는 과정임.
            if begin[j]==words[i][j]:
                standard+=1
                
        if standard==len(begin)-1:#만약 하나 빼고 다 같다면 ==바꿀 수 있다는 뜻.
            copy_words=copy.copy(words) #words를 카피함 이유는 이 다음단어를 돌아야 하기 떄문이다.
            del copy_words[i]#여기서 해당 하나빼고 다 다른 문자열을 제거하고 다시 재귀로 호출
            recursion(words[i],target,copy_words,count+1)

실행 결과