[Lv. 2] 줄 서는 방법

냅다 풀면 오래 걸릴 것 같아서 아이패드에 정리하면서 풀었다. 바로 포스팅을 한게 아니라 생각을 다시 하면서 포스팅을 하고 있다. 막 풀지 말고 깔끔하게 푸는 연습도 해야겠다.

 

우선 전체 경우의 수는 n!개

 

(가지처럼 경우가 뻗어나가는 그림을 상상해보자)

첫번째 자리에 가능한 수 -> n개

두번째 자리에 가능한 수 -> n-1개

세번째 자리에 가능한 수 -> n-2개

.

.

.

n-2번째 자리에 가능한 수 -> 3개

n-1번째 자리에 가능한 수 -> 2개

n번째 자리에 가능한 수 -> 1개

 

이걸 사용해서 첫번째 자리의 수부터 구할 수 있다!

써보면서 풀면 간단하게 해결할 수 있다!

 

import java.util.*;

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

        List<Integer> list = new ArrayList<>();
        long fac = 1;
        int idx = 0;

        // 팩토리얼과 사람 리스트 초기화
        for (int i = 1; i <= n; i++) {
            fac *= i;
            list.add(i);
        }

        // 인덱스를 맞추기 위해 k--
        k--;

        while (n > 0) {
            // 각 자리에 자리에 들어갈 경우의 수
            fac /= n;
            // 자리 숫자 결정
            int val = (int) (k / fac);
            // 정답 배열에 숫자 삽입
            answer[idx] = list.get(val);
            list.remove(val);
            
            // 다음 자리수를 구하기 위해 k값 변경
            k %= fac;
            idx++;
            n--;
        }
        return answer;
    }
}