[プログラマ](Java)-キューの方法

質問リンク

問題を解く

コード#コード#

import java.util.*;

class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        boolean [] chk = new boolean[n+1];

        int idx = 0; //answer에 값을 넣을 위치
        int temp = n; //n 값을 줄여 나갈것이므로 대용으로 쓸 임시값
        
        while(true){
            //마지막 answer 값을 채우고 break;
            if(idx==n-1){
                for(int i=1; i<=n;i++){
                    if(!chk[i]){
                        answer[idx]=i;
                        break;
                    }
                }
                break;
            }
            //배수 ex) 3자리의 경우의 수 = 6 -> 이것은 2 2 2 로 구성되어있다.
            //팩토리얼 돌리는 부분이라고 생각하면된다.
     
            long baesu =1;
            for(int i=1; i<temp; i++){
                baesu *=i;
            }
            //k가 이 배수중 어디에 속해있는지 파악
            //k가 5일때  4<k<=6에 속하므로 kidx = 3 = (i+1)이된다. 
            int kidx = 0;
            for(int i=0; i<temp; i++){
                if(0+i*baesu<k && k<=(i+1)*baesu){
                    kidx = i+1;
                    k -= i*baesu;
                    //System.out.println(k);
                }
            }
            temp--; //다음 팩토리얼 수를 줄이기 위해서...
            //[1, 2, , , ]인 상태에서 
            //kidx 가 2가나오면 사실상 그것은 4를 뜻한다.
            //kidx 보다 작은 값들중에 이미 사용한것들을 체크한다.
            for(int i=1; i<kidx; i++){
                if(chk[i]){
                    kidx++;
                }
            }
            //이미 사용한것은 거르고 i를 증가시켜가며
            //사용하지 않은것을 answer에 넣는다.
            for(int i=kidx; i<=n; i++){
                if(chk[i]){
                    continue;
                }
                answer[idx] =i;
                chk[i] = true;
                break;
            }
            //만약에 위의 로직에서 answer에 값이 들어가지 않는다면
            //1부터 다시 값을 찾는다.
            if(answer[idx]==0){
                for(int i=1; i<kidx; i++){
                    if(chk[i]){
                    continue;
                    }
                answer[idx] =i;
                chk[i] = true;
                break;
                }
            }
            //answer값의 다음 index를 채운다.
            idx++;
        }
        
        return answer;
    }
}