단어변환 (파이썬)

https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3

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

최종 코드

def solution(begin, target, words):
    if target not in words:
        return 0
    level, last_set, words = 0, {begin}, set(words)
    while words and target not in last_set:
        level += 1
        last_set = {word for element in last_set for word in words if 1 == sum(x != y for x, y in zip(element, word))}
        words -= last_set
    return level if target in last_set else 0

테스트 1 〉	통과 (0.01ms, 9.44MB)
테스트 2 〉	통과 (0.13ms, 9.55MB)
테스트 3 〉	통과 (0.88ms, 9.48MB)
테스트 4 〉	통과 (0.02ms, 9.4MB)
테스트 5 〉	통과 (0.00ms, 9.51MB)

 

처음에는 트리를 만들어서 풀까 하다가...
'굳이 트리를 만들 필요가 있나? 그건 너무 빤하잖아. 
반복 횟수만 체크해주는 게 더 빠르고 메모리도 적게 먹을 텐데..'
뭐 이러쿵 저러쿵 해도 결론적으론 너비 우선 탐색이 되어 버린 것... 

 

1. 재귀를 이용함. 
2-1. 같은 레벨에 있어야 할 요소들을 비교 검색하여 하나의 집합(set)에 넣음. 
2-2. 이때 넣은 요소들은 원 리스트에서 삭제하여 반복(순환)을 막음. 
3. 하나의 레벨이 완성되면 남은 리스트들을 재귀로 보내서 반복함. 

 

손가는 데로 막코딩...

def solution(begin, target, words):
    if target not in words:
        return 0

    def match(arr, num):
        temp = set()
        for element in arr:
            for word in words:
                if match_num == len(tuple(True for x, y in zip(element, word) if x == y)):
                    temp.add(word)
                    words.remove(word)
        if target in temp:
            return num
        return match(temp, num + 1)

    match_num = len(begin) - 1
    result = match({begin}, 1)
    return result

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.13ms, 10.2MB)
테스트 3 〉	통과 (0.76ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.00ms, 10.2MB)

정리...

가독성을 생각하면 이 정도에서 멈춰야 하는데..

def solution(begin, target, words):
    if target not in words:
        return 0

    def match(last_set, level):
        new_set = set()
        for element in last_set:
            for word in words:
                if 1 == sum(x != y for x, y in zip(element, word)):
                    new_set.add(word)
                    words.remove(word)
        if target in new_set:
            return level
        return match(new_set, level + 1)

    return match({begin}, 1)

한번 더 정리

def solution(begin, target, words):
    return 0 if target not in words else match({begin}, 1, target, words)


def match(last_set, level, target, words):
    new_set = set()
    for element in last_set:
        for word in words:
            if 1 == sum(x != y for x, y in zip(element, word)):
                new_set.add(word)
                words.remove(word)
    if target in new_set:
        return level
    return match(new_set, level + 1, target, words)

재귀를 반복으로..

def solution(begin, target, words):
    if target not in words:
        return 0
    level, last_set = 0, {begin}
    while words and target not in last_set:
        level += 1
        new_set = set()
        for element in last_set:
            for word in words:
                if 1 == sum(x != y for x, y in zip(element, word)):
                    new_set.add(word)
                    words.remove(word)
        last_set = new_set
    return level if target in last_set else 0

테스트 1 〉	통과 (0.01ms, 9.5MB)
테스트 2 〉	통과 (0.12ms, 9.37MB)
테스트 3 〉	통과 (0.47ms, 9.46MB)
테스트 4 〉	통과 (0.02ms, 9.46MB)
테스트 5 〉	통과 (0.00ms, 9.47MB)