문제 링크

문제 간단 해석

n개 번호의 조합을 오름차순으로 놓고, k번째 값을 가져오는 문제. 그러나 조합식이 아닌, 다른 방식으로 접근해야 시간초과를 피할 수 있다.

Java

풀이 코드

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

class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        List<Integer> pick = new ArrayList<>();
        pick.add(1);
        long div = 1;

        for (int i = 1; i < n; i++) {
            pick.add(i + 1);
            div *= i;
        }

        k -= 1;

        for (int i = 0; i < n - 1; i++) {
            int idx = (int)(k / div);
            answer[i] = pick.get(idx);
            pick.remove(idx);
            k %= div;
            div /= n - i - 1;
        }

        answer[n-1] = pick.get(0);
        return answer;
    }
}

해석

int[] answer = new int[n];
List<Integer> pick = new ArrayList<>();
pick.add(1);
long div = 1;

for (int i = 1; i < n; i++) {
    pick.add(i + 1);
    div *= i;
}

k -= 1;

뽑을 값들의 List와 (n-1)!의 값을 구한다.
그 후 값의 편의를 위해 k에서 1을 빼준다.

for (int i = 0; i < n - 1; i++) {
    int idx = (int)(k / div);
    answer[i] = pick.get(idx);
    pick.remove(idx);
    k %= div;
    div /= n - i - 1;
}

answer[n-1] = pick.get(0);
return answer;

4개 숫자의 조합을 오름차순으로 나열한다고 가정해보자.
맨 앞의 숫자가 변하는 건, 뒤쪽의 숫자 조합이 끝났을 경우3*2*1이다.
프로그래밍은 0부터니, 0부터 센다면 0~5, 6~11, 12~17, 18~23일 때 앞자리가 각각 1, 2, 3, 4일 것이다.

이를 다시 쓰자면, x번째 오름차순 / 3!으로 앞자리가 바뀐다고 볼 수 있으며, 식의 조건에 맞게 쓰면 k / (n-1)!이다.

해당하는 순번의 번호를 가져오고, 목록에서 삭제하는 것으로 다음 카드 선택 시 지장이 없게끔 한다.

한 번 뽑은 후에는 k % div로 다음 카드 선택 시 조건에 맞게끔 해준다.
div 또한 계속해서 줄어들어야 하므로 n-1에서 i를 빼준 만큼 나누어서 이전 팩토리얼 값으로 변경시킨다. (x! / x = (x-1)!)

마지막 숫자 하나만 남았을 경우, 마지막 순번에 넣고 반환한다.

Python

풀이 코드

import math

def solution(n, k):
    answer =  []
    nums = [i for i in range(1, n + 1)]
    n -= 1
    k -= 1

    while n:
        f = math.factorial(n)
        idx = k // f

        answer.append(nums[idx])
        del(nums[idx])

        k %= f
        n -= 1

    return answer + nums

해석

Java와 대동소이함.