백준 구현 대비 순열의 순서

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

접근

permutaions 라이브러리를 활용하여 해결하려 했으나, n의 최댓값이 20까지 가능하다는 점에서 permutations을 사용하여 푸는것은 연산량의 문제로 (20!) 사실상 불가. 다른 해결법을 찾아야함.

오름차순 정렬의 원리와 재귀를 활용하여 해결 할 수 있다.

우리가 만약에 [1,2,3,4] 배열들의 원소를 오름차순으로 정렬한다고 할때,
1번째 부터 6번째 배열은 [1,~,~,~], 7번째부터 12번째 배열은 [2,~,~,~] 그 후는 [3,~,~,~],[4,~,~,~] 이런식으로 정렬될 것이다.
즉 맨 앞자리수가 같은 배열은 n값이 k일때 (k-1)!개씩 존재한다. 이를 활용하여 n을 1씩 줄여가며 count값을 갱신해주면 답을 구할 수 있다.

전체 코드

n = int(input())
m = list(map(int, input().split()))
block = 1
for i in range(1, n + 1):
    block *= i
# n이 4이고 block 이 6
numlist = [i for i in range(1, n + 1)]
if m[0] == 1:
    answer = []
    count = m[1]
    while numlist:
        block= block // n
        idx = (count - 1) // block
        answer.append(numlist.pop(idx))
        count -= idx * block
        n -= 1
    print(*answer)
else:
  m.pop(0)
  count=1
  for num in m:
    block=block//n
    n-=1
    count+=numlist.index(num)*block
    numlist.remove(num)
  print(count)