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

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

프로그래머스

 

모든 경우의 수를 구해서 k번째를 구한다면

가장 큰 경우 n이 20 이하이므로 20! 번 반복문을 돌려야한다.

 

따라서 다 구할수 없고 규칙성을 알아내야한다.

첫번째 숫자를 고정하고 나머지를 구한다면 (n-1)!의 경우의 수이고

m번째 숫자를 고정한다면 결국 (n-m)!의 경우의 수가 나올 것이다.

 

n이 5일때

즉, k가 (5-1)!보다 작다면 첫번째 수는 1로 고정일 것이고 2 * (5-1)!보다 작고  (5-1)!보다 크다면 첫번째 수는 2이다.

그렇다면 두 번째 수는 어떻게 구할까?

2 * (5-1)! - (5 - 1)! 을 해주면 두번째 숫자를 정할 것이다.

3 * (5-2)!보다 작고 2 * (5-2)!보다 크다면 두번째 숫자는 1,2,3,4,5에서 2를 제외한 1,3,4,5중에 4가 될 것이다.

 

Arraylist에 배열을 넣고 해당되는 인덱스를 remove해준다

1보다 작으면 인덱스 0을 remove

 

결국 앞에 곱해지는 수는 1 ~ 남은 자리수 -1 이다.

m은 자리수이다.

코드로 구현해보면 다음과 같다

 

 

import java.util.*;
class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int [n];
        List<Integer> list = new ArrayList<>();
        
        for(int i = 0; i < n; i++) {
            list.add(i + 1);
        }
        int sub = 1;
        int multi = 1;
        for(int i = 0; i < n ; i++) {

            while(true) {
                if(multi * factorial(n - sub) >= k) {
                    k = k -((multi-1) * factorial(n - sub));
                    answer[i] = list.get(multi - 1);
                    list.remove(multi - 1);
                    break;
                } else multi++;
            }
            sub++;
            multi = 1;
        }
        return answer;
    }
    
    public long factorial(int n) {
        long result = 1;
        for(int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
    
}