알고리즘 PS
[Python] 프로그래머스 LV.03 - 단어 변환
on_doing
2021. 3. 13. 18:21
728x90
programmers.co.kr/learn/courses/30/lessons/43163
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
[ 알고리즘 ]
구현
[문제 접근]
bigin부터 덱에 넣어주고, 한글자만 다른지 여부를 판별해준뒤 한글자만 다르다면 덱에 넣어준다
(target이 될 때까지 반복)
[코드]
from collections import deque
def solution(begin, target, words):
cnt = 0
que=deque()
n=len(begin)
if target not in words:
cnt=0
else:
que.append(begin)
while que:
q=que.pop()
if q==begin:
idx=-1
else:
idx=words.index(q) #q의 index부터 검사하면됨
if q == target:
break
cnt+=1
for i in range(idx+1,len(words)):
p=0
word=words[i]
for j in range(n):
if word[j]!=q[j]: #한글자만 다름
p+=1
if p==1:
que.append(word)
return cnt728x90