프로그래머스 - 줄서는 방법 [Python]

 문제

 

 

 문제 상황

 

- permutation은 O(N!)의 속도를 갖기 때문에 permutation을 전부 계산하고 인덱스로 찾으면 속도 이슈가 난다. 그래서 수학적 계산을 해야한다.

 

 

 

 해결 전략

 

 

- 먼저 (n-1)!을 기준으로 나눠 몫만큼 아래로 내려간다. 만약 나머지가 0이라면 n-1번째 요소의 숫자를 리스트의 맨 앞에 두고 남은 리스트 값을 역순으로 하여 붙여준다. 나머지가 0이 아니라면 나머지를 새로운 k로 설정해준다.

 

 

 

 코드

import math
def solution(n,k):
    # n명의 사람 리스트
    lst = [i for i in range(1,n+1)]
    result = []
    # 조건을 만족할 때까지 순회
    while True:
        quo = math.factorial(len(lst)-1)
        # 몫, 나머지
        q, r = divmod(k, quo)
        # 나머지가 0이면 lst의 남은 값들을 역순으로 result에 붙인다.
        if r == 0:
            result.append(lst[q-1])
            lst = lst[:q-1] + lst[q:]    
            result += lst[::-1]
            break
        result.append(lst[q])
        # lst의 q 인덱스 요소를 삭제하고 result에 삽입
        lst = lst[:q] + lst[q+1:]
        k = r
    return result
 
print(solution(3,5))

 

 

 

 

 해설

 

- 완전히 수학적인 문제였다.

 

 새로 학습한 것 & 실수 

 

- .

 

 

출처 - https://programmers.co.kr/learn/courses/30/lessons/12936