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

1. 문제 풀이 아이디어

• k를 팩토리얼 값으로 나누며 순열 그룹을 계산해 k번째 순열을 구할 수 있다.

2. 나의 정답 코드

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

        int count = 0;
        k--;
        while (count < n) {
            f = f / (n - count);
            answer[count++] = list.remove((int) (k / f));
            k = k % f;
        }

        return answer;
    }
}

3. 정리

• 1부터 n까지의 숫자를 리스트에 저장하고, n! (팩토리얼)을 계산해 f에 저장한다.

• k번째 순열을 찾기 위해 k를 1 감소시켜 0부터 시작하도록 조정한다.

• 반복문을 사용해 팩토리얼 값을 활용하여 리스트에서 숫자를 선택하고 순열을 구성한다.
• (n - count) 팩토리얼 값을 f로 업데이트해 현재 그룹 크기를 계산한다.
• k / f를 통해 현재 위치에서 선택할 숫자의 인덱스를 구한다.
• 해당 인덱스의 숫자를 결과 배열에 추가하고, 리스트에서 제거한다.
• k % f로 나머지를 계산하며 다음 그룹으로 이동한다.

• 모든 숫자를 선택할 때까지 반복하며, 결과 배열에 k번째 순열을 저장해 반환한다.