<Hard> Permutation Sequence (LeetCode : C#)

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

📕 문제 설명

주어진 set은 n!의 유일한 순열들을 가진다. n = 3일 때 모든 순열들을 차례로 나열하면 다음과 같다.
"123"
"132"
"213"
"231"
"312"
"321"

n과 k가 주어질 때 k번째의 순열 sequence 반환하기

• Input
  정수 n과 k
• Output
  k번째 순열 sequence

예제

풀이

제일 앞부터 하나씩 채워가는 풀이다.

n! = n * (n-1) * (n-2) * .. * 1 형태이다. 즉, 첫번째 자리를 하나로 고정 했을 때 가능한 경우의 수가 (n-1)!씩 있는 것이다. k번째의 순열을 구하고 싶은 것이니 해당 수를 (n-1)!으로 나눈 몫을 이용해 첫번째 자릿수를 채울 수 있다.

예를들어 n = 4, k = 9이면 첫번째 수가 1, 2, 3, 4가 되는 케이스 별로 3!인 6가지의 경우씩을 가지고 있다. 9번째 수라면 1일때 나오는 6가지 경우를 넘기고 2일때나오는 6가지의 경우 중 3번째라고 볼 수 있다.

이러한 방식으로 모든 자릿수를 k와 현재의 자릿수에 대한 (n-1)!의 몫과 나머지를 이용해 하나씩 채워나가는 식으로 풀었다.

public class Solution {
    public string GetPermutation(int n, int k) {
        
        string answer = "";
        List<int> remainNums = new List<int>();
        int factorial = 1;
        remainNums.Add(1);
        for (int i = 1; i < n; i++)
        {
            remainNums.Add(i + 1);
            factorial *= i;
        }

        k -= 1;
        for (int i = n; i > 0; i--)
        {
            int currentDigit = remainNums[k / factorial];
            answer += currentDigit.ToString();
            remainNums.Remove(currentDigit);
            k = k % factorial;
            if (remainNums.Count > 0)
            {
                factorial /= remainNums.Count;
            }
            
        }

        return answer;
    }
}

결과