[프로그래머스/파이썬] 하노이의 탑

 

나의 풀이 (시간 초과)

def solution(n):
    c1 = [0, 1, 3, 2]
    c2 = [0, 2, 1, 3]
    
    dp = [[]] * n
    dp[0] = [[1,3]]
    
    for i in range(1, n):
        for x in dp[i - 1]:
            dp[i].append([c1[x[0]], c1[x[1]]])
        dp[i].append([1, 3])
        for x in dp[i - 1]:
            dp[i].append([c2[x[0]], c2[x[1]]])
            
    return dp[-1]

 - 횟수로 이해하고 dp로 해결하고자 했다.

 

 

 

나의 풀이 (재귀)

def hanoi(n, a, b, c):
    if n == 1:
        return [[a, c]]
    
    return hanoi(n - 1, a, c, b) + [[a, c]] + hanoi(n - 1, b, a, c)


def solution(n):
    return hanoi(n, 1, 2, 3)

 - 이 경우에는 dp보다 재귀가 빠르다는 것을 알았다. 재사용 되는 것이 없어서 그런 것 같다. (계속 값이 바뀌므로)

 

 

 

yield를 사용한 풀이

def hanoi(n):

    def _hanoi(m, s, b, d):
        if m == 1:
            yield [s, d]
        else:
            yield from _hanoi(m-1, s, d, b)
            yield [s, d]
            yield from _hanoi(m-1, b, s, d)

    ans = list(_hanoi(n, 1, 2, 3))
    return ans

 - yield에 익숙해질 필요가 있다.