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

정리

1. 글자 하나만 차이나는 단어를 찾아 리스트에 append (코드 작성)

2. 제한사항에서 데이터의 길이가 길지 않은 것을 확인할 수 있다. 시간복잡도가 조금 높아져도 통과할 수 있으므로 삼중 반복문도 try 해봐도 된다.

 

- queue를 매번 업데이트 해줘야한다.

- 왜냐하면, 어떤 단어를 기준으로 연관된 단어를 찾을 때마다 queue가 매번 달라질 것임.

- 그렇기 때문에 각 연관 단어를 담을 temp_q를 만들어 iter마다 초기화 해줘야한다. => 난 그 초기화 작업이 없다.

 

주의할 점

1. 어떤 단어와 한 글자만 차이나는 단어가 꼭 하나란 법은 없다. -> 여러개인 경우가 분명 존재함을 인지

2. 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)