Permutation Sequence - LeetCode

Problem

1. input: 정수 n, 정수 k
2. output: n 이하의 수를 한번씩 써서 만들 수 있는 수 중, k 번째로 작은 수 리턴
   • 1 <= n <= 9
   • 1 <= k <= n!

Idea

n 이하의 수를 한번씩만 쓸 수 있기 때문에, n자리 숫자는 n!개 만들 수 있다는 것을 활용

즉, 나눗셈을 통해 앞자리부터 숫자를 정할 수 있다. → Sol1

n자리 수는 (n-1)!마다 1씩 증가 ⇒ n = 4, k = 9 일 때, 가장 앞자리 숫자는 (9/(4-1)! = 1 나머지 3 이므로) 2 이다.

Solution

1. 나눗셈

   k가 1인 경우 만들 수 있는 최솟값을 리턴해야 한다.

   나눗셈을 활용할 경우 0이 첫번째이므로 k - 1 해줘야 한다.

   import java.lang.StringBuilder
   
   class Solution {
   
       fun getPermutation(n: Int, k: Int): String {
           // 사용할 숫자를 담은 리스트 미리 초기화
           val nums = MutableList<String>(n){it->(it+1).toString()}
           val answer = StringBuilder()
           // 1부터 n까지 팩토리얼을 미리 계산
           val dp = Array<Int>(n + 1) { 1 }
           for (i in 2..n) {
               dp[i] = dp[i - 1] * i
           }
           var cnt = k - 1 // 남은 차례 (다음 수)
           var idx = n - 1
           while (nums.size != 0) {
               val tmpCnt = cnt / dp[idx] // 남은 차례에 (n-1)!이 몇번 들어가는지 
               answer.append(nums.removeAt(tmpCnt)) // 몫을 idx로 nums 삽입
               cnt %= dp[idx--]
           }
           return answer.toString()
       }
   }
   

   시간 복잡도: 배열 순회 = n

   

Point