[lv2] 줄 서는 방법

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

 

수학 문제다. 개인적으로 풀이 이후 설명하기 참 난해한 문제라고 느꼈다.

 

 

문제에서 가능한 k의 범위는 1 <= k <= 20!이다.

 

다만, k 값이 long으로 주어지므로 20!이 long 범위를 넘는지는 판단하지 않아도 된다.

 

 

1. 첫번째 원소 판단 (n = 3, k = 5 일 때)

 

n=3 일 때 가능한 수열을 나열하면,

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2] 
[3, 2, 1]

 

찾고자 하는 5번 째 수열 (k = 5)의  첫번 째 수는 3이어야 한다.

 

이는,

n = 3 일 때 전체 경우의 수 (3 * 2 * 1) 에서,

 

(k / 2 * 1) + ( k % 2 * 1 == 0? 0 : 1)

=> 2 + 1 = 3

로 나타낼 수 있다.

 

 

 

2. 다음 탐색을 위한 값 조정

 

첫번째 원소가 3이라는 것을 구했다.

 

다음 탐색을 위해,

2-1. 이미 사용한 3을 원소 list에서 제거한다.

 

2-2.두번째 원소를 찾기위한  k로 조정한다.

e.g.) [3, 1, x]를 구하기 위해선, 결국 [3, x, x]인 수열 목록에서 k = 1번째인 수열을 찾아야 한다.

 

2-3. 첫번째 값을 구하기 위해 (n-1)! 값을 사용했으므로, 두번째 값을 구하기 위한 (n-2)!로 조정한다.

 

 

 

3. 탐색 끝에 원소가 1개 남았다면,

자명한 해이므로, ans에 추가하고 탐색을 종료한다. (+ 안하면 divide by zero 에러 발생)

 

import java.util.*;

class Solution {
    public int[] solution(int n, long k) {

        List<Integer> list = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();

        for(int i=1; i<=n; i++)
            list.add(i);

        int m = n - 1;
        // n번째 수 판단을 위한 (n-1)! 값
        long div = 1;

        for(int i=1; i<n; i++)
            div *= i;

        int cnt = 0;

        while(cnt++ < n) {

            if(list.size() == 1) {
                ans.add(list.get(0));
                break;
            }

            int val = (int) (k / div);
            int mod = k % div == 0? 0 : 1;
            int idx = val + mod - 1;

            ans.add(list.get(idx));
            list.remove(idx);

            k -= div * idx;
            div /= m;
            m--;

        }

        int[] answer = new int[n];

        for(int i=0; i<n; i++)
            answer[i] = ans.get(i);

        return answer;
    }
}