[Programmers][Lv.3] 줄 서는 방법

[문제 링크] - https://programmers.co.kr/learn/courses/30/lessons/12936


문제 설명

제한사항

풀이

import math

def solution(n, k):
    answer = []
    k -= 1  
    order = [i for i in range(1, n+1)]  # 순서 생성
    for i in range(n):
        num = math.factorial(len(order)) 
        temp = num // len(order)       # 현재 차례가 몇가지 경우의 수인지 
        idx = (k // temp)              # 현재 차례가 몇 번째 수가 와야하는지 
        k %= temp                      # 다음 차례가 됨에 따라 차례 재 설정
        answer.append(order.pop(idx))  # 현재 차례 숫자 answer에 
    return answer

처음엔 Permutation을 사용했으나 효율성문제답게 시간초과로 실패하였다.

그래서 다른 풀이를 생각해야 했고, 곧 팩토리얼을 통한 규칙을 찾을 수 있었다.

1. 전체 경우의 수를 몇 개의 묶음으로 나눌 수 있었으며
2. 그 묶음의 순번을 통해 순서를 자리마다 계산하였다.
3. 그리고 다음 자리를 구하기 위해 순번을 재 설정하였다.

처음에 k에 -1을 해준것은 예시들을 넣어봐도
결과값으로 자꾸 다음 차례의 값이 나와서 한번 넣어봤는데 통과했다.
통과한 후에 다른 사람의 풀이들을 보니 k가 딱 나누어 떨어져 0이 되는 경우가 있어서 그런거였다....

그래서 answer.append부분을 다음과 같이 수정하면 좀 더 논리에 맞는 코드가 된다.

if k == 0:
    answer.append(order.pop(idx-1))
else:
    answer.append(order.pop(idx))

결과