문제 - 줄 서는 방법

문제 접근

모든 순열을 구하면서 해당 k번째의 배열을 구하려고했지만 n이 20이하의 자연수로 20!이면 시간초과가 날 것이라고 예상했다.
그래서 패턴을 찾다가 어떻게 해야될지 모르겠어서 다른 사람의 풀이를 보고 이해를 해서 코드를 작성했다.

위에서 15번째에 있는 나열하는 방법을 찾는 방법
배열의 인덱스는 0부터 시작하여 14번째를 찾으면 된다.
1. 첫번째 원소를 구하는 방법

2. 두번째 원소를 구하는 방법

이런 방법으로 원소를 구하면 k번째의 방법을 찾을 수 있다.

import java.util.*;

class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        ArrayList<Integer> ary = new ArrayList<>();
        
        //총 경우의 수 n!
        long total = 1;
        for(int i=1;i<=n;i++)
        {
            ary.add(i);
            total *= i;
        }
        //배열의 인덱스는 0부터 시작하여 찾아야될 번호를 -1
        k--;
        
        int idx = 0;
        while(idx < n)
        {
            //전체 경우의 수 / 숫자의 갯수
            total /= n - idx;
            //해당 인덱스의 값의 숫자 가져오기
            answer[idx++] = ary.remove((int) (k/total));
            //다음 찾아야될 번호
            k %= total;
            
        }
        return answer;
    }
}