[프로그래머스] 줄 서는 방법 (python)

https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

 

 

문제에서 k는 n! 이하의 자연수라고 나와있다. 이 문장이 힌트이다.

 

문제의 예시를 보자. 맨 앞의 숫자가 1일 때 1을 맨 앞의 원소로 갖는 리스트는 [1, 2, 3], [1, 3, 2]이다.

 

이 개수는 (n - 1)!이다. 문제 보기는 n = 3이므로 리스트 개수는 2개 이다.

 

그 리스트 안에서 2로 시작하는 리스트는 [1, 2, 3]이다.

 

이 개수는 (n - 2)!이다. 뭔가 규칙이 보인다.

 

각 자리수로 내려가면서 인덱스 값을 (n - 1)!, (n - 2)!, … 로 나눈 값을 number의 인덱스로 사용해서 빼주면 되는 문제이다.

import math

def solution(n, k):
    answer = []
    number = [i for i in range(1, n + 1)]

    while number:
        perm = math.factorial(n - 1) # 현재 자리수의 순열 개수
        idx = (k - 1) // perm # k 값을 인덱스에 맞추기 위한 1 걈소
        answer.append(number.pop(idx)) # 위에서 구한 인덱스 값을 answer에 삽입
        k = k % perm # 현재 자리수의 순열 개수로 나눈 나머지로 조정
        n -= 1 # n을 줄여 다음 자리로 이동

    return answer

 

references

https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스