[연습 문제 / 프로그래머스] 12936번 : 줄 서는 방법

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

 

Lv2 문제다!

(n - 1)!만큼 i번째 수가 각 인덱스에 있는 걸 발견했지만, 이를 어떻게 구현해야할지 몰랐던 문제다.

이번 기회를 통해서 이 부분 공부해야겠다 

 

참고한 블로그

 

문제 이해 

• permutation으로 구하면 시간이 오래 걸리므로, 다른 방법을 사용해야한다 
• 문제를 보면 1부터 n으로 시작하는 배열이 각각 n! // n == (n - 1)! 개씩 있다 
• k 를 (n - 1)!로 나눈 몫(k // (n - 1)!)이 정답 배열에 추가되는 수이므로 answer에 추가한다 
• temp에서는 해당 수를 사용했으므로 pop해준다 
• k를 (n - 1)!로 나눈 나머지, n은 -1 해준다
• 위의 연산을 총 n번 반복한다 

- 정답 풀이 : 

 

import math

def solution(n, k):
    temp = [x for x in range(1, n + 1)]
    answer = []
    k -= 1
    
    # n번 반복 
    for _ in range(n, 0, -1):
        max_num = math.factorial(n)
        split_num = max_num // n
        
        answer.append(temp[k // split_num])
        temp.pop(k//split_num)
        
        k %= split_num
        n -= 1
        
    return answer