프로그래머스.하노이의 탑.python

하노이 타워 규칙성 찾기

우선 n = 2일때의 결과를 블록 A라 하자

==============
n = 2
결과 : [A]

블록 A	블록 @A @ => 2 & 3 교체	블록 #A # => 1 & 2 교체
1 -> 2 1 -> 3 2 -> 3	1 -> 3 1 -> 2 3 -> 2	2 -> 1 2 -> 3  1 -> 3

==============
n = 3
결과 : [@A , B , #A]
==============
n = 4

@( [@A , B , #A]) + B + #( [@A , B , #A])
결과 : ['A', '@B', '@#A', 'B', '#@A', '#B', 'A']

==============
n = 5

@(['A', '@B', '@#A', 'B', '#@A', '#B', 'A']) + B + #(['A', '@B', '@#A', 'B', '#@A', '#B', 'A'])

결과 : ['@A', 'B', '#A', '@B', '@#@A', '@#B', '@A', 'B', '#A', '#@B', '#@#A', '#B', '@A', 'B', '#A']
...

도출된 식: F(x+1) = @*F(x) + B + #*F(x)

필요 변수	나올 수 있는 경우
A  B  @  #	A @A #A @#A #@A @#@A #@#A B @B #B @#B #@B @#@B #@#B

연산규칙 & 테이블
B 1 -> 3 #B 2 -> 3 @B 1 -> 2 @#B 3 -> 2 #@B 2 -> 1 @#@B 3 -> 1 #@#B 3 -> 1 @#@#B = #@B 2 -> 1 #@#@B = @#B 3 -> 2	#A       @#A      #@#A    @#@#A = #@A 2 -> 1  3 -> 1    3 -> 2      2 -> 3 2 -> 3  3 -> 2    3 -> 1      2 -> 1 1 -> 3  1 -> 2    2 -> 1      3 -> 1 @A      #@A     @#@A    #@#@A = @#A 1 -> 3  2 -> 3    3 -> 2      3 -> 1 1 -> 2  2 -> 1    3 -> 1      3 -> 2 3 -> 2  3 -> 1    2 -> 1      1 -> 2

테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.04ms, 10.2MB)
테스트 4 〉	통과 (0.07ms, 10.2MB)
테스트 5 〉	통과 (0.06ms, 10.3MB)
테스트 6 〉	통과 (0.12ms, 10.3MB)
테스트 7 〉	통과 (0.25ms, 10.3MB)
테스트 8 〉	통과 (0.63ms, 10.4MB)
테스트 9 〉	통과 (0.86ms, 10.6MB)
테스트 10 〉	통과 (1.85ms, 11.1MB)
테스트 11 〉	통과 (3.72ms, 12.4MB)
테스트 12 〉	통과 (7.09ms, 14.4MB)
테스트 13 〉	통과 (14.19ms, 16.3MB)

def solution(n):
    Trans_dic = {
        'A': [[1,2], [1,3], [2,3]],
        '#A': [[2,1], [2,3], [1,3]],
        '@A': [[1,3], [1,2], [3,2]],
        '#@A': [[2,3], [2,1], [3,1]],
        '@#A': [[3,1], [3,2], [1,2]],
        '@#@A': [[3,2], [3,1], [2,1]],
        '#@#A': [[3,2], [3,1], [2,1]],
        'B' : [[1,3]],
        '#B' : [[2,3]],
        '@B' : [[1,2]],
        '@#B' : [[3,2]],
        '#@B' : [[2,1]],
        '@#@B' : [[3,1]],
        '#@#B' : [[3,1]],
    }
    def calculation(cl):
        if "@@" in cl:
            return cl.replace("@@", "")
        elif '##' in cl:
            return cl.replace('##', "")
        elif "#@#@" in cl:
            return cl.replace("#@#@", "@#")
        elif "@#@#" in cl:
            return cl.replace("@#@#", "#@")
        else:
            return cl

    def formula(block):
        new_block = []
        for i in range(len(block)):
            new_block.append( calculation( ''.join(['@',block[i]]) ) )
        new_block.append('B')
        for i in range(len(block)):
            new_block.append( calculation( ''.join(['#',block[i]]) ) )
        
        return new_block
    
    result = []
    block = ['A']

    if n == 1:
        return [[1,3]]
    
    for _ in range(n-2):
        block = formula(block)

    for st in block:
        result.extend(Trans_dic.get(st))

    return result