[프로그래머스][줄 서는 방법]

프로그래머스 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

 

문제를 풀다가 우연히 수학공식을 발견하게 되어서 위 글을 쓰게 된다.

 

 숫자가  [1,2,3]

이 있을시 

1 2 3 

1 3 2

2 1 3 

3 1 2

 

이 순으로 나열할수 있는데 

조금더 n 을 크게 하여서 일반화를 시킬수 있다. 

 

예를 들어 1 ,2 , 3, 4 ,5 가 있으며

49번째 수를 구할때에는 

1 이 가장 앞에나올때는 4! 의 경우가 있으며

2 가 가장 앞에나올때는 4! 의 경우가 있으며 

다음 3이 나올때의 49 - 4!*2 번째 수를 구하면 된다. 

 

이를 생각을 하다가 

 

n! =  (n-1)*(n-1)! + (n-2)*(n-2)!  + (n-3)*(n-3)! + ......... 1*1! + 1 이라는 것을 알게 되었다. 

 

증명은 k! - (k-1)*(k-1)! = (k-2)! 이라는것을 계산하기만 하면 자연스럽게 증명을 할수있다. 

각설하고...

 

위를 토대로 n 장의 숫자카드로 만들수있는 경우는 n! 인데 

 

n! 은 팩토리얼 의 합으로 나타낼수있다는 것을 알아냈다. 

이는 

 

가장 앞에 나오는 카드의 숫자를 구한다음에 기존에 가지고있는 배열에 

그숫자를 뺸 이후 , 

새롭게 얻을 배열과 , 새롭게 얻어진 k번쨰의 숫자를 구하여 재귀함수 형식으로 구할시  코드를 빠른시간안에 완성시킬수 있다는 것을 알수있게 된다. 

 

코드는 다음과 같다. 

import math

def get_array(array, n, k):
    if n==1:
        return array
    
    tmp_factorial = math.factorial(n-1)
    for i in range(1,n+1):
        if k <= i*tmp_factorial:
            # i 번째수 빼고 뒤로가면댐
            target_number = array[i-1]
            array.remove(target_number)
            
            return [target_number] + get_array(array,n-1, k- (i-1)*tmp_factorial)
    

def solution(n, k):
    array = [i for i in range(1,1+n)]
    return get_array(array, n, k)