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

프로그래머스_줄 서는 방법

처음에 permutations으로 모든 경우의 수를 돌렸는데 정확성은 다 맞았지만, 효율성이 전부 시간초과가 났다.

내 오답 코드

from itertools import permutations

def solution(n, k):
    cnt = 0
    for p in permutations(range(1,n+1)):
        if cnt==k-1:
            answer = list(p)
            break
        cnt+=1
    
    return answer

답안 코드

결국 다른 분의 코드를 참고했다

• 총 경우의 수는 n!
• num_case = n!/n 이므로 앞 자리 숫자 1~n인 경우가 각각 몇 개씩인지 확인 가능
• k번째를 구해야하므로 k//num_case가 idx가 된다
• k%num_case가 0이 되면 딱 맞아 떨어지므로 idx-1을 answer에 넣어준다
• 0이 아니라면 idx번째를 넣어준다

import math

def solution(n, k):
    answer = []
    num_list = [i for i in range(1,n+1)]
    while n!=0:
        num_case = math.factorial(n-1)
        idx = k//num_case
        k = k%num_case
        if k==0:
            answer.append(num_list.pop(idx-1))
        else:
            answer.append(num_list.pop(idx))
        n-=1
    
    return answer

이게 LV2라니,, 알고리즘이 아닌 그냥 규칙을 찾는 문제가 더 어려운 것 같기도 하다ㅠ_ㅠ