[프로그래머스] level2 12936 - 줄 서는 방법(Java)

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

접근 방법

1. 순서있는 순열을 만든다.

그런데 20!는 너무 많다. 포기

2. 규칙을 찾는다.

앞자릿수가 무엇인지 하나씩 찾아가며 접근한다.
n=4, k=10일 때

1. 앞자릿수가 변하는 구간은 6개씩(3!) 지날때이다.
2. k/6 -> 앞자릿수
3. k%6 -> 앞자릿수가 정해진 뒤, 남은 순서
4. list에서 앞자릿수를 제외하고, res에 추가시킨다.
5. k를 줄이고, 반복

소스 코드

import java.util.*;

class Solution {
    
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        long[] dp = new long[n+1];
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1]*i;
        }
        
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(i+1);
        }
        List<Integer> res = new ArrayList<>();
        
        while(true){
            long num = dp[n-1];
            if(k % num == 0){ // 맨 앞의 숫자가 정해진 상태에서 마지막 순서인 경우
                res.add(list.remove((int)(k/num) - 1));
                break;
            } else{
                res.add(list.remove((int)(k/num)));
                k%=num;
            }
            n--;
        }
        
        if(!list.isEmpty()){
            for(int i=list.size()-1;i>=0;i--){
                res.add(list.get(i));
            }
        }
        
        for(int i=0;i<res.size();i++){
            answer[i] = res.get(i);
        }
        
        return answer;
    }
}