[프로그래머스/Swift] 12946번 - 하노이의 탑

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12946

💡 구현 아이디어

A→C로 N개 원판을 이동하려면 A→B로 N-1개 원판을 이동하고 A→C로 원판을 이동해야한다.

💻 코드

import Foundation

func solution(_ n:Int) -> [[Int]] {
    var path: [[Int]] = []
    
    func hanoi(_ n: Int, _ start: Int, _ end: Int, _ sub: Int) {
        if n == 1 { 
            path.append([start, end])
            return 
        }
        hanoi(n-1, start, sub, end)
        path.append([start, end])
        hanoi(n-1, sub, end, start)
    }
    
    hanoi(n, 1, 3, 2)
    return path
}

❌ 틀린 이유 및 틀린 부분

⏳ 시간 복잡도

O(2^n): 한번의 함수에서 두개의 호출을 다시 진행

📌 풀이 또는 기억할 정보

https://mgyo.tistory.com/185

https://velog.io/@bky373/알고리즘-기초-하노이-탑-알고리즘