[파이썬] 프로그래머스 : 줄 서는 방법 (Lv.2)

[파이썬] 프로그래머스 : 줄 서는 방법 (Lv.2)

 

프로그래머스

 

---

풀이

방향성 생각

재귀적으로 위치 파악

ex) n=5 일 때 94번 째?
n! = 120 / [0, 24, 48, 72, 96] / (n-1)! 맨 앞사람 단위로 변한다. -> 94가 어느 범위에 있냐? 94가 4번째는 못넘음.

현재 인원 [1,2,3,4,5] 중 4번째 가져옴. -> 남은 인원 [1,2,3,5]

94-72 = 22 22에 대해서도 똑같이 진행 
ex) n=4 일 때 22번 째?
n! = 24 / [0,6,12,18] / (n-1)! 맨 앞사람 단위로 변한다. -> 22가 어느 범위에 있냐? 94가 4번째는 못넘음.
현재 인원 [1,2,3,5] 중 4번째 가져옴 -> 남은 인원 [1,2,3]

 

전체코드

def solution(n,k):
    factorial = [1]
    for i in range(1,n+1):
        factorial.append(factorial[-1]*i)

    def location(n,k,arr):
        if n == 0:
            return []
        f = factorial[n-1]
        idx = (k-1)//f
        num = arr.pop(idx)
        return [num] + location(n-1,k-idx*f,arr)

    arr = list(range(1,n+1))
    return location(n,k,arr)