[프로그래머스/Java] 줄 서는 방법

-Code

import java.util.*;

class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        List<Integer> nums = new ArrayList<>();
        // n! 계산 및 nums에 수 저장
        long fac = 1;
        for (int i = 1; i <= n; i++) {
            nums.add(i);
            fac *= i;
        }
        // 인덱스가 0부터이므로 조정
        k--;
        // 자리수 하나하나 계산
        for (int i = 0; i < n; i++) {
            // 다음 자리 묶음의 크기 계산
            fac /= (n - i);
            // k를 묶음으로 나눈 몫이 현재 자리의 수 인덱스
            int idx = (int) (k / fac);
            answer[i] = nums.get(idx);
            // 사용한 숫자 제거
            nums.remove(idx);
            // 숫자를 사용했으므로 k 갱신
            k %= fac;
        }
        return answer;
    }
}

처음에 백트래킹으로 풀려했으나 시간 초과 문제를 겪게 되었습니다. 그래서 찾아보니 펙토리얼을 통한 규칙을 찾아 해결해야 했습니다.

 

예를 들어 n=4, k=7일 때를 계산해보면 아래와 같습니다.

1. 첫 번째 자리 결정:
   • 숫자가 1, 2, 3, 4 네 종류 존재
   • 각 숫자가 맨 앞에 올 때마다 뒤에 올 수 있는 경우의 수는 (4-1)! = 6가지입니다.
   • 1이 맨 앞인 경우: 1~6번째
   • 2가 맨 앞인 경우: 7~12번째 -> 우리가 찾는 7번째는 여기 묶음에 존재합니다.
   • 따라서 첫 번째 숫자는 2입니다.
2. 두 번째 자리 결정:
   • 이제 남은 숫자는 1, 3, 4이고, 남은 순서는 k=7에서 앞의 6개를 뺀 1번째입니다.
   • 각 숫자가 앞에 올 때마다 (3-1)! = 2가지씩 생깁니다.
   • 1이 맨 앞인 경우: 1~2번째 -> 우리가 찾는 1번째는 여기에 있습니다.
   • 따라서 두 번째 숫자는 1입니다.

이런 식으로 나눗셈의 몫과 나머지를 이용해 자리를 찾아가야 합니다.

이를 통해 조금씩 구현하고 부족한 부분은 힌트를 찾아 조금씩 해결하는 식으로 해서 통과하였습니다.