프로그래머스 - 줄 서는 방법

내 풀이

import java.util.*;
class Solution {
    int[] answer;
    long index =0;
    
    public int[] solution(int n, long k) {
        String s ="";
        for(int i=1; i<=n; i++){
        s+=String.valueOf(i);
        }
        dfs("",s,n,k);
        return  answer;
    }
    public void dfs(String currStr, String others,int n,long k ){
        if(currStr.length()==n){
           index++; 
            if(index ==k) {
                answer= new int[n];
                for(int j=0; j<currStr.length(); j++){
                answer[j]= currStr.charAt(j)-'0';
                }
                return ;
            }
        }
        for(int i=0; i<others.length(); i++){
            dfs(currStr+ others.charAt(i), others.substring(0,i)+others.substring(i+1),n,k);
            
        }
    }
   
}

dfs로 풀면 시간 초과

답
각 자리수마다 반복적으로 등장하는 횟수가 정해져 있음
첫째 자리수의 경우 (n-1)!, 둘째 자리수 (n-2)! ...
k에서 각 자리수가 몇번째 반복 구간에 해당하는지 구하고 이를 빼는 과정을 반복하면 구할 수 있다.

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