input :
- n, k
output :
- n!의 순열에 대해서 k번쨰 순열을 반환하시오.
조건 :
Solution explain : Solution1
idea
- 재귀로 구성하는 경우에 시간복잡도가 문제가 된다.
- 현재 char를 사용할 때 몇개의 순열을 뛰어넘는지를 계산하는 방식을 쓰자.
- 첫자리에 놓을 char를 결정할 때면, 그 뒤에 있는 개수만큼의 순열이 존재할 수 있다.
- 그래서 cnt_permutation이란 변수를 통해서 그 개수를 체크한다.
- 그러면 char가 늘어날수록 뒤에 오는 개수가 줄어드니까 biggest_idx라는 변수로 이를 제어 한다.
주의
class Solution:
def getPermutation(self, n: int, k: int) -> str:
can_use = dict()
for i in range(1, n + 1):
can_use[i] = 1
cnt_permutation = 1
biggest_idx = n - 1
for i in range(1, n):
cnt_permutation *= i
ret = ""
while k != 0:
for key in can_use.keys():
if can_use[key] == 0:
continue
if k <= cnt_permutation:
ret += f"{key}"
can_use[key] = 0
break
k -= cnt_permutation
if biggest_idx == 0:
break
cnt_permutation = cnt_permutation // biggest_idx
biggest_idx -= 1
return ret