[Programmers] 줄 서는 방법 - 12936

특징 잘 파악해서 풀기

 

Question

 

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

 

Point

 

• k -= 1 : 1부터 시작하는 인덱스를 0으로 바꿔주기 위해 1을 빼줍니다.
• f = fact(len(p)-1) : 현재 남아 있는 숫자의 수가 m 이라면, 해당 자리에서 한 숫자가 고정됐을 때 나머진 순열의 개수는 (m-1)! 입니다. ex) n=3일 때, 첫 번째 자리 숫자가 고정되면 남은 숫자로 만들 수 있는 순열의 개수는 2! = 2 입니다.
• answer.append( p.pop( k//f ) ) : k//f 는 현재 자리에 올 숫자의 인덱스를 나타냅니다.
• k = k%f : 현재 자리 선택이 끝난 후, k를 업데이트 합니다.

Example

 

n = 3일 때, [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]

 

• 첫 번째 자리가 1인 순열: [1,2,3],[1,3,2]
• 첫 번째 자리가 2인 순열: [2,1,3],[2,3,1]
• 첫 번째 자리가 3인 순열: [3,1,2],[3,2,1]

 

각 그룹의 크기는 동일하며, 나머지 n−1개의 숫자로 만들 수 있는 순열의 개수와 같습니다. 즉, 각 그룹은 (n−1)! 개의 순열을 포함합니다.

 

• k번째 순열이 속한 그룹은 k를 (n−1)!로 나눈 몫으로 결정됩니다.
• 예를 들어, n=3,k=5인 경우:
  • (n−1)!   =   2!   = 2 
  • k  =  5−1  =  4 (0 기반 인덱스를 사용하기 위해 k에서 1을 뺌)
  • k//(n−1)!  =   4//2   =   2 
    • 이는 k번째 순열이 세 번째 그룹(index 2인 그룹)에 속한다는 것을 의미합니다.
    • 세 번째 그룹의 첫 번째 숫자는 3입니다.

 

• 즉, 정리하자면
  • k // (n-1)!  =>  어느 그룹에 속하는지를 나타냅니다.
  • k % (n−1)!  =>  해당 그룹 내에서 몇 번째 순열인지 나타냅니다.

 

 

Code

 

from math import factorial as fact
def solution(n, k):
    answer = []
    p = list(range(1,n+1))
    
    k -= 1
    while p:
        f = fact(len(p)-1)
        answer.append( p.pop( k//f ) )
        k = k%f
        
    return answer

 

now me

On my github