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

문제 링크

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

문제풀이

맨처음 dfs로 풀다가 시간초과가 나서 방향을 바꿨다.
k의 값을 통해서 앞에서부터 answer에 값들을 채워넣는 방식으로 구현했으며
나만 알아볼수 있게 문제를 푼거같다.

문제를 풀기위한 나의 배경지식은 이랬다.
1 2 3 4 로 수열을 만들때
나오는 가짓수는 24(4!)개이다.
여기서 맨 앞에 하나를 정해놓고 수열을 만들면 6가지(3!)으로 경우의 수가 줄어든다.
그렇게 된다면 1로 시작하는것 6개, 2로 시작하는것도 6개 .. 4로 시작하는것도 6개와 같이 접근이 가능하다.

그래서 2로 시작하는 수열은 적어도 k가 7일때부터 등장한다.

이렇게 k가 11인 경우 수열은 2로 시작하는 수열중에 하나일것으로 생각이 가능하다.

그 다음 k-6을 해준다. (왜냐하면 앞에 있는 1로 시작하는 수열은 신경쓸필요 없기 떄문에 6을 뺀다.) 그러면 k=5이고 2 x x x 가된다.
다시 앞의 로직을 반복해서 3!에 대해 1로 시작하는것 2개, 3으로 시작하는것 2개, 4로 시작하는것 2개가 된다.
k는 5이므로 4로 시작하는 수열중에 하나라는 뜻이된다.
그러면 k-4를 해준다. 그리고 4를 넣어 2 4 x x 를 만들어 준다.
k는 1이므로 2!에 대해 1로 시작하는것 1개, 3으로 시작하는것 1개중에
1로 시작하는것에 속하므로 2 4 1 x가 되고 마지막 남은것은 3밖에 없으므로 3을 넣어준다.
그렇게 되면 2 4 1 3이 된다. 이것을 이제 아래 코드로 구현했다.

코드

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;
    }
}