[BOJ]1722. 순열의 순서

문제:

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개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

풀이방법:

 한 문제에 K번째 수열을 구하는 문제와 주어진 수열이 몇 번째인지 구하는 문제가 합쳐져 있다. 두 소문제는 주어진 수 중 맨 앞의 숫자로 구별되며, 이를 command(c)로 구분해 각 소문제를 풀도록 한다.

 첫 번째 소문제는 K번째 수열을 구하는 문제다. 앞의 자릿수부터 계산하며, 주어진 수 K로부터 만들 수 있는 경우의 수를 빼주며 한자리씩 정해나간다. 즉, 예제의 경우 3번째 수열을 구하는 문제에서 맨 앞자리를 a인 경우의 수는 3!개이다. 따라서 3번째 수열은 0~3!번째 수열에 속할 것이므로, 맨 앞자리는 1인 것을 알 수 있다. 이러한 방법을 계속하여 k번째 수열을 찾는다.

 두 번째 소문제는 첫 번째 소문제의 역으로 구할 수 있다. 팩토리얼을 사용해 k번째 수열을 구했던 것의 역으로 팩토리얼을 더하면서 k를 찾도록 한다.

N = int(input())
tmp = list(map(int,input().split()))
c, numbers = tmp[0],tmp[1:]
factorial = [0]*21
factorial[0] = 1
for i in range(1,21):
    factorial[i] = factorial[i-1]*i
if c==1:
    answer = []
    numbers = numbers[0]
    used = [0]*(N+1)
    for i in range(N):
        for j in range(1,N+1):
            if used[j]==1:
                continue
            if factorial[N-i-1]<numbers:
                numbers-=factorial[N-i-1]
            else:
                used[j]=1
                answer.append(j)
                break
    print(*answer)
elif c==2:
    answer = 0
    used = [0]*(N+1)
    for i in range(N):
        for j in range(1,numbers[i]):
            if used[j] == 0:
                answer += factorial[N-1-i]
        used[numbers[i]] = 1
    print(answer+1)

문제링크:

https://www.acmicpc.net/problem/1722

1722번: 순열의 순서