[백준 1722번] 순열의 순서 (Python/파이썬)

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

1722번: 순열의 순서

분명 그냥 수학문제로 간단해 보였는데 왜 틀렸는지 모르겠다.

처음에 한번 구현하고 왠만한것들 잘 통과 되길래 제출했는데 계속 틀렸다고 나와서 조금씩 수정하다가

스트레스 받아서 지우고 다시 짰더니 바로 통과...

알고리즘은 똑같이 짰는데 뭐가 틀린건지..

코드는 다음과 같다.

 

import sys
import math
input = sys.stdin.readline
n = int(input())
problem = list(map(int,input().split()))
case = [0] * n; case[0] = math.factorial(n)
for i in range(1,n):
  case[i] = case[i-1] // (n+1-i)
used = [False] * (n+1)

if problem[0] == 1:
  k = problem[1]
  find = [0] * (n)
  for i in range(n):
    for j in range(1,n+1):
        if not used[j]:
          if i+1 < n:
            if case[i+1] >= k:
              find[i] = j
              used[j] = True
              break
            else:
              k -= case[i+1]
          else:
            find[i] = j
  print(*find)
else:
  seq = problem[1:]
  order = 1
  idx = 1
  for i in seq:
    tmp = 0
    for j in range(1,n+1):
      if not used[j]:
        tmp += 1
        if i == j:
          break
    if idx < n:
      order += (tmp-1) * case[idx]
    idx += 1
    used[i] = True
  print(order)