[LeetCode 풀이/python] 60. Permutation Sequence (hard)

문제 설명: 정수 집합 [1, 2, 3, ..., n] 은 총 n! 개의 고유한 순열(permutations) 을 포함한다. 모든 순열 조합을 순서대로 나열해서 레이블링을 하면, n = 3 일 경우의 시퀀스는 다음과 같다:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

n , k 가 주어졌을 때, k 번째 순열 시퀀스를 리턴하시오.

 

(The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3: (생략) Given n and k, return the kth permutation sequence.)

 

예시 1)

입력: n = 3, k = 3  -->  출력: "213"

 

예시 2)

입력: n = 4, k = 9  -->  출력: "2314"

 

예시 3)

입력: n = 3, k = 1  -->  출력: "123"

 

제한 조건:

• 1 <= n <= 9
• 1 <= k <= n!

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • n 자리 숫자의 순열 조합은 n x (n-1)! 개가 존재하며, 이를 나열 후 0 부터 레이블링하면 해당하는 레이블 (k-1) 은 a * (n-1)! + b 의 형태로 표현할 수 있음
    • (ex) n = 3, k = 3: 2 = 1 * 2! + 0
  • 이 때 0 <= a < n 으로서, a+1 은 해당 순열의 맨 앞자리 수 1 ~ n 를 가리키는 요소가 되며,
  • b 는 해당 숫자 (a+1) 로 시작하는 순열 조합 중 해당 순열이 몇 번째인지를 가리키는 요소라고 할 수 있음  -->  맨 앞 자리 숫자를 제외한 다음 자릿 수부터 b 를 k 로 간주하여 동일하게 적용 
  • 순열은 각 숫자가 각 자릿수를 표현하는 데에 한 번씩만 사용되므로 이전에 사용된 숫자는 제외(pop) 하고 남은 숫자들 중에서 순서를 매겨 사용함
  • 이런 식으로 찾고자 하는 k 번째 순열의 맨 앞 자리 숫자에서부터 차례로 찾아낼 수 있음

 

• 코드 구현

def getPermutation(n: int, k: int) -> str:
    res = ""
    cand = list(range(1, n+1))

    while cand:
        div, mod = divmod(k-1, math.factorial(n-1))
        digit = cand.pop(div)
        n -= 1
        k = mod + 1
        res = res + str(digit)
            
    return res

 

 

• 결과
• • 길이 n 인 배열 cand 를 선형으로 순회하는 데에 O(n) & 매번 임의의 인덱스에 위치한 아이템을 꺼내는(pop) 데에 O(n)  -->  총 O(n^2) 의 시간 복잡도 요구됨
  • 하지만 제한 조건 상 n 이 최대 9 의 값을 가지는 정도라 O(n^2) 의 계산량 매우 작음... 무사히 통과...