[코테] 순열 - 줄 서는 방법[프로그래머스]

문제:

출처: 프로그래머스 - 줄 서는 방법 : https://school.programmers.co.kr/learn/courses/30/lessons/12936#qna

풀이:

1. itertools의 permutations

from itertools import permutations
def solution(n, k):
    nlist = [i for i in range(1, n+1)]
    nlen = len(nlist)
    cnt = 0
    answer = []
    # permutations은 리스트와 그 리스트에서 n가지를 골라 순열로 반환한다.
    for i, v in enumerate(permutations(nlist, nlen)):
        cnt += 1
        if cnt == k: # k번째의 해당 순열을 반환
            answer = list(v)
            break
    return answer

1번과 같이 풀이를 진행할 시 모든 순열을 모두 확인하며 진행하기에 시간 초과가 난다.
n가지의 순열을 구하는 경우의 수는 n!, 즉 (factorial:순열의 경우의 수)는 'n! = n × (n-1) × (n-2) ×....3 × 2 × 1'으로써 길이가 20이라면 다음과 같은 경우의 수를 가진다.

1!    1
2!    2
3!    6
4!    24
5!    120
.     720
.     5040
.     40320
.     362880
10!   3628800 - 300만의 연산
.     39916800
.     479001600
.     6227020800
.     87178291200
.     1307674368000
.     20922789888000
.     355687428096000
.     6402373705728000
19!   121645100408832000
20!   2432902008176640000

그렇기에 k번재의 자릿수를 바로 확인하여 찾는 수 밖에 없다.
그렇다면 사전 순으로 늘어놓았을 때 규칙성을 찾아서 그 규칙성에 맞도록 그 경우의 수를 찾아야 한다.
수학적인 소양을 요구하기에 까다로운 문제다.

2 자리수 확인하기

규칙성을 확인해보자.
n = 5라면,
120가지의 경우의 수를 다 봐야 하기에 앞자리가 1인 경우만 가져와 보겠다.

(1, 2, 3, 4, 5)
(1, 2, 3, 5, 4)
(1, 2, 4, 3, 5)
(1, 2, 4, 5, 3)
(1, 2, 5, 3, 4)
(1, 2, 5, 4, 3)
(1, 3, 2, 4, 5)
(1, 3, 2, 5, 4)
(1, 3, 4, 2, 5)
(1, 3, 4, 5, 2)
(1, 3, 5, 2, 4)
(1, 3, 5, 4, 2)
(1, 4, 2, 3, 5)
(1, 4, 2, 5, 3)
(1, 4, 3, 2, 5)
(1, 4, 3, 5, 2)
(1, 4, 5, 2, 3)
(1, 4, 5, 3, 2)
(1, 5, 2, 3, 4)
(1, 5, 2, 4, 3)
(1, 5, 3, 2, 4)
(1, 5, 3, 4, 2)
(1, 5, 4, 2, 3)
(1, 5, 4, 3, 2)

위와 같이 24가지가 있다.

그렇다면 n = 4인 경우에 앞자리가 1인 경우의 수는 아래와 같이 6가지가 있다.

(1, 2, 3, 4)
(1, 2, 4, 3)
(1, 3, 2, 4)
(1, 3, 4, 2)
(1, 4, 2, 3)
(1, 4, 3, 2)

이렇게 n의 제일 앞의 자리수가 1인 경우는 (n-1)! 가지가 있는 경우의 수를 확인할 수 있다.
만약 n = 5 라면 24번째까지는 앞자리가 1이며, 25번부터 앞자리의 수가 2로 바뀌는 것을 확인할 수 있다. 그래서 k = 30이라면 앞의 자리수는 2라는 것을 확인할 수 있는 것이다.

이런 규칙성을 통해 k번째의 수는 n번째 자리의 (n-1)을 나눈 몫의 자리를 구한다면 각각의 자리를 확인할 수 있게 된다.
n = 5, k = 30일 때(파이썬은 0부터 시작을 하니 30번째는 29번째의 수를 구하는 것이다.),
n = [1, 2, 3, 4, 5]

1. '29 // (5-1)! = 1'(4! = 24)이므로 첫번째 자리수는 1번째 인덱스로 2가 들어가게 된다.
   이렇게 몫은 자릿수가 되며, 나머지는 구한 자리수의 다음 k번째 자리를 구하는 수가 된다. 왜냐하면 24번째까지는 앞자리가 1이며 30번째는 앞자리가 2가 되었으니, 2가 된 후부터 5번째를 구하면 그것이 두 번째 자리수가 되는 것이다.
2. '5 // (4-1)! = 0'이므로 남은 인덱스 중 0번째 인덱스는 1이되다. 그리고 나머지는 5이다.
3. '5 // (3-1)! = 2'이므로 남은 인덱스 중 2번째 인덱스는 5이며, 나머지는 1이다.
4. '1 // (2-1)! = 1'이므로 남은 인덱스 중 1번째 인덱스는 4가 된다. 나머지는 0이다.
5. '0 // (1-1)! = 0'이므로 남은 마지막 수는 3이 된다.

이렇게 몫은 자릿수가 되며 나머지는 다음 인덱스를 정할 순번이 되는 규칙성을 가지고 있다.

코드:

from math import factorial
def solution(n, k):
    k -= 1 # 파이썬은 0부터 시작하기에.
    nlist = list(range(1, n+1))
    answer = []
    for i in range(n, 0, -1):
        fact = factorial(i-1)
        idx = k // fact # 몫 구하기: 자리수
        k %= fact # 나머지 구하기: 다음 자리수의 순번
        answer.append(nlist.pop(idx)) # 몫이 해당 자리수이기에 업데이트한다.
    return answer