[LeetCode] 60. Permutation Sequence

https://leetcode.com/problems/permutation-sequence/

Permutation Sequence - LeetCode

Permutation Sequence - Hard

 

1에서 n까지의 숫자가 한번씩 쓰여 이루어진 수가 있다. 이 수들을 나열했을때, k번쨰로 작은 수를 구하는 문제다.

이 문제는 중/고등학교 경우의 수에서 많이 보이는 문제다.

앞자리부터 구해나가면 되는데, 가장 앞자리를 구하는 방법은 아래와 같다.

 

만약 4자리 수이고, k가 9라고 하자.

맨 앞자리가 가장 작은 1로 시작하면, 1 _ _ _ 가 만들어지는 경우의 수는 3! = 6 이다.

2,3,4 도 마찬가지일 것이다. 따라서 6번째로 작은 수까지는 1이 가장 앞 자리수이고, 그 후로는 2가 가장 앞에 와야한다.

이 때, k를 보면 9로, 6보다 크다. 또한 12보단 작다.

그러므로 우리가 구하는 가장 앞 자리수는 1보단 크고 3보단 작은 2가 된다.

이제 2로 시작하는 수들 중 k=> 9-6 = 3번째로 작은 수를 구하면 된다.

가장 작은 수의 앞자리는 1로 시작할 것이고 2 1 _ _ 은 2! = 2개가 있다.

역시나 k가 2보다 크고 4보다 작으므로, 두번째 자리수는 1보단 크고 (2가 없으므로) 4보다 작은 3이 된다.

k => 3-2 = 1

이제 2 3 _ _ 중 가장 작은 수를 구하면 된다.

그렇다면 가장 작은 수부터 써주면 되므로 구하는 수는 2 3 1 4 가 된다.

이를 그대로 코드로 구현하면 된다.

 

전체 풀이 코드

class Solution {
public:
    string getPermutation(int n, int k) {
        int factorial[10]={1,}, nums[10]={};
        string ret;
        for (int i=1; i<=n; i++) factorial[i] = i*factorial[i-1], nums[i]=1;
        k--;
        n--;
        while(n>=0) {
            int a = k / factorial[n],c=0,i=1;
            for (; !nums[i] || c<a;i++) if (nums[i]) c++; 
            ret += i+'0';
            nums[i]=0;
            k-= factorial[n--] * a;
        }
        return ret;
    }
};