[programmers] 줄 서는 방법

06 Apr 2023 in Algorithm on Algorithm

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

int index = (int)(k / factorial[n-1-i]); 이부분에 대한 이해가 한참 안되었다. 핵심은 전체를 나누는 게 아니라, 해당 자리에서 선택지를 몇 개씩 묶어서 나뉘는지에 따라 나눔이다.
즉, n = 4, k = 14일 경우 앞자리가 몇번씩 반복되는지 파악하는 것이 중요하다.

ex) 아래와 같을때 6번씩 나온다.

맨앞숫자	범위
1	1 ~ 6
2	7 ~ 12
3	13 ~ 18
4	19 ~ 24

import java.util.*;

class Solution {
    public int[] solution(int n, long k) {
        List<Integer> numbers = new ArrayList<>();
        long[] factorial = new long[n+1];
        
        factorial[0] = 1;
        for(int i = 1; i <= n ; i++){
            factorial[i] = factorial[i -1] * i;
            numbers.add(i);
        }
        
        k--;
        int[] answer = new int[n];
        
        for(int i = 0; i <n ; i++){
            int index = (int)(k / factorial[n-1-i]);
            answer[i] = numbers.get(index);
            numbers.remove(index);
            k %= factorial[n-1-i];
        }
        
        return answer;
    }
}