[LeetCode # 60] Permutation Sequence

주어진 문제는, 주어진 n, k 에 해당하는 순열을 찾는 것이다. n (1 <= n <= 9) 은 순열에 포함되는 수의 개수이고, k (1 <= k <= n!) 는 순열의 순서이다.

 

예를 들어, (n, k) 가 (3, 3) 으로 주어졌다면 기대되는 출력값은 "213" 이 된다. 위의 그림에서 보여지듯, "123", "132", "213", ... 의 순서로 순열을 생성할 수 있고, 그 중 k 번째 수열은 "213" 이다. (1-indexed)

 

이 문제를 해결하기 위한 전략은 다음과 같다. n 이 3일 때 생성되는 순열은 "123", "132" / "213", "231" / "312", "321" 이다. '/' 로 나눠놓은 것을 보면 각각 수열이 갖는 첫번째 수가 같은 것끼리 묶여있음을 알 수 있고, 이를 바탕으로 문제를 해결할 수 있음을 유추할 수 있다.

 

(n, k) 가 (4, 7) 로 주어진 경우를 생각해 보면, n 이 4이므로 사용 가능한 숫자들의 목록은 [1, 2, 3, 4] 가 된다. 세 개의 숫자로 구성할 수 있는 수열은 6개이므로 "1", "2", "3", "4" 로 시작하는 각각의 수열의 개수는 6개임을 알 수 있다. 이 때, 각 숫자의 순서대로 수열이 순서를 가지므로 k 가 7이라는 것은, "2" 로 시작하는 수열을 찾고자 함을 알 수 있고, 그 중 1번째 수열임을 알 수 있다.

 

이러한 방식으로, 첫 번째 숫자를 찾고 그 뒤에는 남은 [1, 3, 4] 를 통해 앞으로 어떤 숫자들이 수열에 순서대로 위치할 지를 찾아낼 수 있다. 문제를 풀이한 소스 코드는 다음과 같이 작성했다.

 

class Solution {
public:
    int factorial(int n) {
        int result = 1;
        while (n > 1) {
            result *= n--;
        }

        return result;
    }

    string getPermutation(int n, int k) {
        vector<int> nums;
        for (int i = 1; i <= n; i++) {
            nums.push_back(i);
        }

        string ans = "";

        while (n > 1) {
            int blockSize = factorial(n - 1);
            int block = k / blockSize;
            k %= blockSize;

            ans += to_string(nums[block]);
            nums.erase(nums.begin() + block);
            n--;
        }

        return ans + to_string(nums[0]);
    }
};