사람의 수 n과, 자연수 k가 주어질 때,사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return
제한사항
n은 20이하의 자연수
k는 n! 이하의 자연수
"""
입출력 예시)
n = 3, k = 5 -> [3,1,2]
"""
## 의사코드 ##
# n명의 사람이 줄을 서는 방법 -> permutations
# 먼저, n명의 사람이 있을 때, 각각 1부터 n까지의 번호를 매김
# -> people = [i for i in range(1, n+1)]
# people 리스트를 permutations로 줄을 서는 방법 구함
# method = list(permutations(people, n))
# -> 자동으로 사전 순으로 나열됨
# method 리스트에서 (k-1)번째 원소 return
# -> 리스트에서는 인덱스가 0부터니까
첫 번째 시도
from itertools import permutations
def solution(n, k):
people = [i for i in range(1, n+1)]
method = list(permutations(people, n))
return list(method[k-1])
-> permutations()로 모든 경우의 수를 다 구해서 k번째 방법을 return
-> 추가 테스트 케이스 실패, 효율성 테스트 실패(시간 초과)
(정확성: 63.2 / 효율성: 0.0)
통과한 코드
## 의사코드 ##
# permutations로 모든 경우의 수를 다 구해서 k번째 방법을 return하는 게 아니라
# n!을 이용해서 인덱스로 k번째 방법에 나왔을 숫자를 하나씩 구하는 방법
# n명의 사람이 줄을 서는 방법의 수 = n!
# -> math.factorial(n)
# 먼저, n명의 사람이 있을 때, 각각 1부터 n까지의 번호를 매김
# -> people = [i for i in range(1, n+1)]
# 그리고 k -= 1 (리스트의 인덱스가 0부터 시작)
# 맨 첫 번째 숫자가 같은 경우의 수는 n! // n 개
# -> split_n = n!//n
# answer의 첫 번째 숫자 -> people[(k // split_n)]
# 이걸 answer에 append하고,
# people 리스트에서는 pop으로 제거 -> pop(인덱스)
# k를 k % split_n으로 변환
# n에서 1을 빼서 다시 n!을 계산하도록
# -> 이 과정을 n번 반복
# => for i in range(n, 0, -1) # n부터 1까지 -1씩
import math
def solution(n, k):
answer = []
people = [i for i in range(1, n+1)]
k -= 1
for i in range(n, 0, -1):
split_n = math.factorial(n) // n
answer.append(people[k//split_n])
people.pop(k//split_n)
k %= split_n
n -= 1
return answer
-> n!을 이용해서 인덱스로 k번째 방법에 나왔을 숫자를 하나씩 구함
맨 첫 번째 숫자가 같은 경우의 수 = n! // n 개
맨 첫 번째 수가 1인 경우 = n!//n개
맨 첫 번째 수가 2인 경우 = n!//n개
...
맨 첫 번째 수가 n인 경우 = n!//n개
n = 3
k = 5
from itertools import permutations
people = [i for i in range(1, n+1)]
method = list(permutations(people, n))
print(method)
"""
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
"""
import math
n_fac = math.factorial(n)
print('n!:', n_fac)
print('n! // n:', n_fac // n)
"""
n!: 6
n! // n: 2
"""
-> n이 3일 때, 모든 경우의 수는 n!인 6개
-> 모든 경우의 수를 보면(method) 맨 첫 번째 숫자가 1인 경우가 2개, 2인 경우도 2개, 3인 경우도 2개
