[python] 백준 - 1722. 순열의 순서

🤔문제 해결

S1 | 수학, 조합론

순열을 보면 itertools의 permutation이 생각난다. 하지만 이 문제에서는 N이 20까지 이므로 20!을 구하는것은 불가능.

 

먼저 소문제1일 때의 경우를 살펴보자.

N = 5, K = 35 일 때(5개의 숫자, 35번째 순열)

N = 5 이므로 5! = 120이다. 120 / N 으로 나누면 24가 되는데, 이는 각각의 앞자리 5개가 가지는 경우의 수이다.

앞자리가 1이면 1 ~ 24번째, 앞자리가 2이면 25 ~ 48번째, 앞자리가 3이면 49 ~ 72번째 ... 이다.

 

K = 35이면 25~48이므로 앞자리가 2라는 것을 알 수 있다.

다음 스텝으로 넘어가면 n = 4, k = 35 - 24 = 11이다. 즉, 맨 2 이전의 숫자인 1이 맨 앞자리에 오는 경우는 24가지를 전부 지나치고 2가 맨 앞일 때 11번째 숫자를 찾는 경우이다.

다시 말해서

N = 4, K = 11 일 때로 넘어오게 된다.

이 과정을 재귀로 구현하여 값들을 뽑아보면 다음과 같이 나오게 된다.

테스트 예시

예시에선 2 3 5 1 까지 보인다. 그 이유는 마지막 자리는 숫자가 하나 남았기 때문에 그 때만 남은 숫자를 채워주고 함수를 종료시켰다.

답은 2 3 5 1 4 가 나오게 된다.

 

다음은 소문제2일 때의 경우를 살펴보자.

순열이 주어지면 그게 몇 번째 순열인지 알아내야 한다.

N = 5, K = 2, 3, 5, 1, 4 일 때

N = 5, 5! = 120, 120 / N = 24이다. 

맨 앞자리가 2이므로 25 ~ 48 에 포함되어 있다. +24

그 다음 3이므로 다음 7 ~ 12 에 포함되어 있다. +6

그 다음 5이므로 다음 5 ~ 6 에 포함되어 있다. +4

그 다음 1이므로 다음 1 ~ 1 에 포함되어 있따. + 1

마지막 4는 자동으로 결정 되므로 위의 숫자들을 더하면 35가 나오게 된다!

 

💨 수학문제는 손으로 풀어보고 규칙을 찾아보는게 좋다.

 

💻소스 코드

import math


def find_one(n, k):
    if len(answer) == N - 1:
        answer.append(numbers[-1])
        return

    numberOfCases = math.factorial(n) // n
    sequence = math.ceil(k / numberOfCases)
    answer.append(numbers.pop(sequence))

    find_one(n-1, k-(numberOfCases*(sequence-1)))


def find_k():
    n = N
    for num in K:
        numberOfCases = math.factorial(n) // n
        idx = numbers.index(num)
        if len(numbers) == 2:
            idx += 1
            answer.append(numberOfCases*idx)
            return
        numbers.pop(idx)
        answer.append(numberOfCases*idx)
        n -= 1


if __name__ == "__main__":
    N = int(input())
    tmp_input = list(map(int, input().split()))
    order = tmp_input.pop(0)

    # 소문제 1
    if order == 1:
        K = tmp_input[0]
        numbers = [x for x in range(N+1)]
        answer = []
        find_one(N,K)
        print(' '.join(list(map(str, answer))))

    # 소문제 2
    else:
        K = tmp_input
        numbers = [x for x in range(1, N+1)]
        answer = []
        find_k()
        print(sum(answer))
        
        
        

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

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