[ 프로그래머스 / PYTHON ] 줄 서는 방법

문제 설명

줄 서는 방법
n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

[1, 2, 3][1, 3, 2]
[2, 1, 3][2, 3, 1]
[3, 1, 2][3, 2, 1]
사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항
n은 20이하의 자연수 입니다.
k는 n! 이하의 자연수 입니다.

풀이 & 코멘트

풀고보면 쉬운데 이런 수학적 문제 + 인덱스 활용 하는 문제는 한번 헷갈리면 죽을 때까지 헷갈려서 결국 처음 풀다가 포기하고 다른사람 설명(코드x 마지막 양심이랄까) 본 후 다른날 다시 풀었다

🔎다시푼 후기
다시 풀어도 저 수학 공식이 가물가물해서 저 공식만 다시봄 (거의 답 뺴낀수준인가 ^9^..) 다시풀 때는 공식만 보고 코드 작성하는데 저번처럼 인덱스 안 헷갈림 ^8^...

코드

22.07.08

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

    def line(k,li):
        nonlocal answer
        if k == 0 or len(li) ==0 :    
            answer = answer + li
            return
        else:
            s,r = divmod(k-1,math.factorial(len(li)-1))
            answer.append(li.pop(s))
            line(r+1,li)

    line(k,li)
    return answer

22.08.09 위랑 별 다를 거 없음 한달만에 풀어서 그런가 디게 쉽게 기억?생각해내서

import math
def solution(n, k):
    answer = []
    li = [ i+1 for i in range(n)]
    
    def line(k,li):
        nonlocal answer
        if len(li) == 1 :   
            answer.append(li[0])
        else:
            idx,nk = divmod(k,math.factorial(len(li)-1))
            answer.append(li.pop(idx))
            line(nk,li)            
    
    line(k-1,li)
    return answer