[1722] 순열의 순서 in python

itertools에 있는 permutation 함수를 사용하여 

문제를 풀었더니

당연히 메모리 초과,,, 큽..

import itertools

n = int(input())
array = list(map(int, input().split()))
temp = list(itertools.permutations(range(1, n + 1), n))
# array[0] = 소문제 번호
if array[0] == 1:
    # k를 입력받음 -> array[1]에 있음
    print(*temp[array[1] - 1])
else:
    # 임의의 순열을 나타내는 n개의 수를 입력받음
    # array[1:n+1]
    print(temp.index(tuple(array[1:n + 1])) + 1)

 

직접 구현해야하나 고민했지만,

이것도 마찬가지로 메모리초과가 뜰 것 같았다.

 

그래서 구글링을 결국 해보았는데

생각도 못했던 방식으로 문제를 풀어서 놀랐다..

 

정말 이 발상을 어떻게 떠올려내는지

그들은 천재...

 

삐약이 같은 나는 아직도

갈 길이 멀다 ! !

 

 

 

1일 때

 

2일 떄

import itertools

n = int(input())
array = list(map(int, input().split()))


def factorial(inp):
    if inp <= 1:
        return 1
    else:
        return inp * factorial(inp - 1)


if array[0] == 1:
    k = array[1]
    nums = list(range(1, n + 1))
    temp = []

    for i in range(n, 0, -1):
        fac = factorial(i - 1)
        step = (k-1) // (fac)  # idx 문제 때문에
        temp.append(nums[step])
        del nums[step]
        k -= fac * step  # 이 부분이 가장 생각해내기 어려웠음.
    print(*temp)

else:
    li = array[1:]
    nums = list(range(1, n + 1))
    k = 1
    for i in range(n, 0, -1):
        fac = factorial(i - 1)
        step = nums.index(li[n-i])
        del nums[step]
        k += fac * step
    print(k)