난이도

Gold 5

인증

문제

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

출력

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

예제 입력

4
1 3

예제 출력

1 3 2 4

해설 및 후기

처음엔 간단하게 itertools의 permutation으로 해결하려고 했으나, 이내 시간과 메모리가 부족함을 깨닫게 되었다. 따라서 보다 수학적으로 접근하고자 했다. 먼저 1번이 입력되는 소문항의 경우, 각 자리의 숫자는 뒤에 남은 숫자의 갯수의 팩토리얼로 나누어 정할 수 있었다. 중복을 제거하는 방식으로 구할 수 있었다.

2번이 입력되는 소문항의 경우에도 마찬가지로 각 숫자를 순회하며, 자릿수 별로 얼마 만큼의 순열을 지나왔는지 구하여 모두 더해 구한다.

제출 코드

n = int(input())
s = list(map(int, input().split()))
fact = [1]
r = 1
c = [False for _ in range(21)]
for i in range(1,22):
    r*=i
    fact.append(r)

if(s[0] == 1):
    k = s[1]
    res = []
    for i in range(n):
        for j in range(1,n+1):
            if(c[j] == False):
                if(k > fact[n-1-i]):
                    k -= fact[n-1-i]
                else:
                    res.append(j)
                    c[j] = True
                    break
        
    for i in res:
        print(i, end=' ')
else:
    res = 0
    for i in range(n):
        for j in range(1, s[i+1]):
            if(c[j]==False):
                res += fact[n-1-i]
        c[s[i+1]] = True
    print(res+1)