하노이의탑(yield)

프로그래머스의 하노이의 탑 문제

import copy

def solution(n):
    answer = [[1,3]]
    for i in range(n-1):
        temp=copy.deepcopy(answer)
        for j in range(len(temp)):
            for k in range(len(temp[0])):
                if temp[j][k]==1:temp[j][k]=2
                elif temp[j][k]==2:temp[j][k]=1
        for j in range(len(answer)):
            for k in range(len(answer[0])):
                if answer[j][k]==2:answer[j][k]=3
                elif answer[j][k]==3:answer[j][k]=2

        answer.append([1,3])
        answer+=temp
    
    return answer

아이디어는 최종적으로 모두 3번기둥으로 옮겨야 하므로 n층의 탑일 경우 n-1층의 탑을 옮기는 과정을 2번기둥으로 옮기는 과정으로 바꾼 후 2번기둥을 모두 3번기둥으로 옮기면 되므로 n-1의 답을 2,3을 바꾼 후(3번기둥 대신 2번기둥으로 옮기기) [1,3]을 더한 후(가장 큰 층을 3번기둥으로) n-1의 답을 1,2를 바꾼 값(2번기둥에서 3번기둥으로 이동) 을 더해주는 것이다.

 

deepcopy를 사용해서 list를 복사한 후 값을 변경해 더해주었다.

 

다른 사람의 풀이중 인상적이었던 풀이는 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

 

아이디어는 똑같이 n-1번째의 답에서 기둥을 바꾸고 [1,3]을 더하는 것이지만 훨씬 깔끔하고 보기 편하다.

yield의 기능은 순차적으로 출력하는 것으로

 

def simple_generator():
    yield 1
    yield 2
    yield 3

for value in simple_generator():
    print(value)

1
2
3

이런 식으로 사용할 수 있고 list를 사용하면

print(list(simple_generator()))


#[1,2,3]

이렇게 사용할 수 있다.

 

 

내가 작성한 코드와의 차이는

시간복잡도는 둘 다 O(2^n)이지만 공간복잡도는 내가 작성한 코드는 deepcopy를 사용해 매 반복마다 전체 리스트를 복사하므로 최악의 경우 O(2^n)에 가깝지만 yield를 사용할 시 재귀 함수의 최대 깊이인 O(n)이 된다.