정리
- 글자 하나만 차이나는 단어를 찾아 리스트에 append (코드 작성)
- 제한사항에서 데이터의 길이가 길지 않은 것을 확인할 수 있다. 시간복잡도가 조금 높아져도 통과할 수 있으므로 삼중 반복문도 try 해봐도 된다.
- queue를 매번 업데이트 해줘야한다.
- 왜냐하면, 어떤 단어를 기준으로 연관된 단어를 찾을 때마다 queue가 매번 달라질 것임.
- 그렇기 때문에 각 연관 단어를 담을 temp_q를 만들어 iter마다 초기화 해줘야한다. => 난 그 초기화 작업이 없다.
주의할 점
- 어떤 단어와 한 글자만 차이나는 단어가 꼭 하나란 법은 없다. -> 여러개인 경우가 분명 존재함을 인지
- tmp_q (임시 queue)의 필요성을 인지할 것
실패한 풀이
마지막 테스트케이스에서 실패, 모가 문제인지 아직 모르겠다.
def solution(begin, target, words):
queue = [begin]
answer = 0
while queue:
tmp_q = []
curr = queue.pop(0)
if curr == target:
return answer
for i in range(len(words) - 1, -1, -1):
temp = [1 for a, b in zip(curr, words[i]) if a != b]
if sum(temp) == 1:
tmp_q.append(words.pop(i))
answer += 1
queue = tmp_q
if not words:
return 0
통과한 코드 (다른 사람 풀이)
- 사실 이 풀이는 O(n^3) 이기 때문에 별로 내키지 않았는데, 제한 사항에서 words의 길이가 최대일 경우가 50 이기에 삼중 반복문도 괜찮다.
def solution(begin, target, words):
answer = 0
queue = [begin]
while queue:
tmp_q = []
for word1 in queue:
if word1 == target:
return answer
for word2_idx in range(len(words)-1, -1, -1):
word2 = words[word2_idx]
difference = sum([x != y for x, y in zip(word1, word2)])
if difference == 1:
tmp_q.append(words.pop(word2_idx))
if not tmp_q:
return 0
queue = tmp_q
answer += 1
- 두번째 for문에서 range()내부 인자를 차감식으로 작성하였는데, 이렇게 한 이유는 for문 내부에서 words를 pop()할 때, indexError를 방지하기 위함이다.
- word2_idx는 words 리스트의 마지막 인덱스부터 첫 인덱스로 차감되기 때문에, words.pop(word2_idx)를 할 때 뒤에서 부터 pop() 할 수 있다. (인덱스가 꼬일 위험 X)
