PS/문제 풀이
[프로그래머스/Swift] 12946번 - 하노이의 탑
시르베어
2025. 4. 16. 11:36
🔗 문제 링크
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): 한번의 함수에서 두개의 호출을 다시 진행