[Programmers / Level 2] 12936. 줄 서는 방법 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12936
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/줄 서는 방법

입출력 조건

입출력 예시

문제 이해

• n명의 사람이 있을 때, k번째 순열을 찾는 문제

알고리즘

풀이 시간 : 12분

• nums 리스트에 1부터 n까지 숫자를 넣음
• k번째 순열은 각 자리에서 (k / (n-1)!)번째 숫자부터 시작
• 팩토리얼 배열을 미리 계산해 시간 절약
• 각 자리에 들어갈 숫자를 계산 후 리스트에서 제거
• k--로 0-based index로 조정

import java.util.*;

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

        int[] result = new int[n];
        long[] factorial = new long[n + 1];
        factorial[0] = 1;

        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        k--;

        for (int i = 0; i < n; i++) {
            long f = factorial[n - 1 - i];
            int idx = (int) (k / f);
            result[i] = nums.remove(idx);
            k %= f;
        }

        return result;
    }
}

결과