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

문제

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

코딩테스트 연습 - 줄 서는 방법

 

접근법

처음에는 재귀로 모든 경우의 수를 찾고 k 번째 경우의 수에서 재귀를 멈췄다.

이런 방법으로 하면 k가 long으로 선언된 변수이므로 너무 많은 재귀가 돌아갔다.

그래서 찾은 방법은 k를 줄여나가는 방식이다.

숫자가 n 개인 경우에 정렬할 수 있는 모든 경우의 수 점화식은

dp[n] = dp[n-1] * n 이다.

숫자가 1개일 때는 1가지이고 2개일 때는 2가지, 3개일 때는 6가지, 4개일 때는 24가지가 된다.

n=4, k=10인 경우를 예로 들겠다.

n=4인 경우에는 dp[4] = dp[3] * 4 = 24가지의 경우의 수가 있다.

맨 앞자리	뒷자리
1	2 3 4
	2 4 3
	3 2 4
	3 4 2
	4 2 3
	4 3 2
2	1 3 4
	1 4 3
	3 1 4
	3 4 1
	4 1 3
	4 3 1
3	1 2 4
	1 4 2
	2 1 4
	2 4 1
	4 1 2
	4 2 1
4	1 2 3
	1 3 2
	2 1 3
	2 3 1
	3 1 2
	3 2 1

위의 표를 보면 숫자가 3개인 경우의 수(6가지)가 4개만큼 있는 것을 알 수 있다.

여기서 k=10번째는 6 + 4 로 맨 앞자리가 2일 때의 4번째 경우의 수라는 것을 알 수 있다.

이를 통해 맨 앞 자리가 2라는 사실은 이미 정해졌다.

그러면 뒤의 세 개의 수만 놓고 보면 된다.

맨 앞자리	뒷자리
1	3 4
	4 3
3	1 4
	4 1
4	1 3
	3 1

위의 표에서 4번째 경우의 수를 찾으면 된다.

위의 표에서도 역시 숫자가 2개인 경우(2가지)가 3개 만큼 있다는 것을 볼 수 있다.

그러면 k=4번째는 2 + 2로 맨 앞자리가 3인 경우의 2번째 경우라는 것을 알 수 있다.

이렇게 k를 줄여나가면서 맨 앞자리부터 정해나가면 빠르게 답을 찾을 수가 있다.

 

코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        List<Integer> res = new ArrayList<>();
        List<Integer> list = fillList(n);
        long dp[] = totalCount(n);

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

    private List<Integer> fillList(int n) {
        List<Integer> list = new ArrayList<>();
        for(int i=1;i<=n;i++){
            list.add(i);
        }

        return list;
    }

    private long[] totalCount(int n) {
        long dp[] = new long[n+1];

        dp[1] = 1;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1] * i;
        }

        return dp;
    }

}