1. 동작

https://gist.github.com/nansu0425/ba0135eb954a8f14eb9ce16ffc2f30c8

2. 특징

  • 반복문에서 매 반복마다 leftIdx부터 rightIdx까지의 문자열 순서가 유지되도록 swap을 두 번 수행한다
  • rightIdx는 고정돼 있고 leftIdx는 재귀 호출할 때 마다 하나 씩 증가한다

3. 성능

  • 시간 복잡도
    • 출력해야 하는 순열 개수는 문자열의 문자 개수를 $n$이라고 할 때 $_{n}P_{n} = n!$
    • 문자열 출력 시 모든 문자 $n$개를 순차 탐색한다
    • 따라서 시간 복잡도는 $O(n * n!)$
  • 공간 복잡도
    • 함수의 스택 프레임은 leftIdx가 1 증가할 때마다 쌓인다
    • leftIdx는 rightIdx까지 증가하므로 쌓이는 스택 프레임의 최대 개수는 rightIdx와 leftIdx의 차에 비례한다
    • rightIdx를 $r$, leftIdx를 $l$이라고 할 때 공간 복잡도는 $O(r - l)$

4. 참고 자료