[7급 국가직 자료구조론 2023년 6번]

다음 하노이 탑 문제를 해결하는 파이썬(Python) 코드의 시간 복잡도는? (단, n은 원판의 개수이고 first, second, third는 기둥 번호이다)

def hanoiT(n, first, second, third):
  if n == 1:
    print("원판1 : %s 에서 %s"%(first, third))
  else:
    hanoiT(n - 1, first, third, second)
    print("원판%d : %s 에서 %s"%(n, first, third))
    hanoiT(n - 1, second, first, third)