(Python/LV2)줄 서는 방법

문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

풀이:

import math
from itertools import permutations
def solution(n, k):
    arr = [i for i in range(1,n+1)]
    res = []
    while n != 0:
        fac = math.factorial(n-1)
        idx , k = (k-1)//fac, k % fac
        res.append(arr.pop(idx))
        n -= 1
    return res

조합 쓰려다가 이거 이렇게 쉽게 낼 문제 아니라고 생각해서 시도조차 안함

n-1 / k-1 / -1 씩 하는 이유 0 부터 인덱싱을 해야함

 

1. n이 2일경우 1개씩 나오고 // n이 3일경우 2게씩 //n이 4일경우 6개씩 즉 (n-1)! 나누기 n 만큼씩 반복된다

2. (k-1) // fac 을 하면 2 가 나오는데 [1,2,3] 중에 2를 뜻한다 

    2-1 (k-1)개씩 똑같은 숫자가 반복되기때문에 위처럼 계산함  ex(3,5) 인 경우 4 //2 몫은 2가 남아 [3] 이 도는 차례라 [3] 을 가져옴

3 나머지는 다시 추가해주고 똑같이 반복

    3-1 안에서 안에서 도는 갯수가 -1 더해서 팩토리얼만큼 되기때문

 

(k-1 // fac) 이 부분이 생각하는데 오래걸렸다