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

https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

접근 방법

1. 가장 처음에 순열을 구현해서 k 번째에 ans를 저장하여 return하는 방법을 사용했다 => 시간초과
   
   1. 20! 을 부르트 포스로 구하려했으니 당연하다
2. 브루트포스가 아닌 바로 k 번째 수를 찾아야한다
3. 순열n의 가지수는 n!이므로 n * (n-1)! 의 가지수를 갖는다 즉
   1. 1xxxx 가(n-1)! 개, 2xxxx 가 (n-1)!개 ... nxxxx 가 (n-1)!개 가 있다는 뜻이된다
   2. 따라서 k 번째에 첫번째 수는 소수점을 버린 (k / (n-1)!) 이 된다
   3. 첫번째 k = M*(n-1)! + a  라고 할 수 있는데 a를 무시하고 (n-1)!로 나누어 M번째 수를 구했으니
   4. 다음 두번 째 K는 a라고 할 수 있으므로 k = k % (n-1)! 이 된다
   5. 이런 식으로 그다음 번째 수도 이미 나온것을 제외하고, k를 업데이트 하며 구할 수 있다

코드

import java.util.*;
class Solution {
    public int[] solution(int n, long k) {
        long num = 1;
        List<Integer> list = new ArrayList<>();
        
        for(int i = 1 ; i<= n ; i++){
            list.add(i);  
            num*=i;
        } 
        
        int[] ans = new int[n];
        int idx = 0;
        k--;
        
        while (idx < n){
            num = num / (n - idx);
            ans[idx++] = list.remove((int)(k/num));
            k= k % num;
        }
        
        return ans;
    }
}