Java에서 팩토리얼을 이용한 K번째 순열 찾기

팩토리얼(factorial)

수학에서 주어진 양의 정수보다 작거나 같은 모든 양의 정수의 곱을 의미하며 기호로는 n!로 표시한다.

예시

7의 팩토리얼은 7!로 표시하며, 1 × 2 × 3 × 4 × 5 × 6 × 7을 의미
5의 팩토리얼은 5!로 표시하며, 5 × 4 × 3 × 2 × 1 = 120을 의미

---

순열(permutation)

어떤 집합의 원소들을 특정한 순서로 배열하는 것.

예시

1, 2, 3 세가지 숫자로 순열을 만들 경우

1. [1, 2, 3]
2. [1, 3, 2]
3. [2, 1, 3]
4. [2, 3, 1]
5. [3, 1, 2]
6. [3, 2, 1]

---

---

K번째 순열을 찾는 원리

정렬된 순열에서 K번째 순열을 찾고 싶을 경우 n개의 숫자를 포함하는 순열의 총 개수는 n!이다.

1. 첫 번째 숫자 찾기
   가장 앞에 올 숫자는 (k-1) / (n-1)! 번째 요소로 결정된다.
   예를 들어, n=3, k=5일 때:
   (5-1) / (2!) = 4 / 2 = 2 → 3번째 숫자가 첫 번째 자리
2. 남은 숫자로 반복
   k를 (n-1)!로 나눈 나머지를 새로운 k 값으로 사용하여 위 과정을 반복한다.

이 방식을 활용하면 모든 순열을 생성하지 않고도 K번째 순열을 빠르게 찾을 수 있다.

---

예시 코드

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

public class Test_71_HowToLineUp {
    public int[] solution(int n, long k) {
        List<Integer> numbers = new ArrayList<>();
        long fact = 1;
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
            fact *= i;  // n! 계산
        }

        int[] answer = new int[n];
        k--; // 0-based index로 변환

        for (int i = 0; i < n; i++) {
            fact /= (n - i);  // (n-i)! 값
            int index = (int) (k / fact); // 현재 선택할 숫자의 인덱스
            answer[i] = numbers.get(index);
            numbers.remove(index); // 사용한 숫자 제거
            k %= fact; // 다음 k값 업데이트
        }

        return answer;
    }
}

입력 값 :
int n = 3
int k = 5
출력 값 :
int[] result = {3, 2, 1}

---

시간 복잡도

팩토리얼 계산 : O(n)
순열 생성 과정 : O(n)
ArrayList remove 연산 : O(n) (최대 n번)
총 시간 복잡도 : O(n²)

모든 순열을 생성하는 방식(O(n!))보다 효율적이다.