[알고리즘] 프로그래머스 - 줄 서는 방법

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

통과 못한 내 풀이

from itertools import permutations

def solution(n, k):
    people = [i for i in range(1, n+1)]
    answer  = list(permutations(people, n))
    return list(answer[k-1])

시간초과가 난다. 20!이다.

다른 사람 풀이

import math
def solution(n, k):
    answer = [num for num in range(1,n+1)]
    answer_list = []
    while n > 0 :
        n -= 1
        share, remainder = divmod(k,math.factorial(n))
        if not remainder: share -= 1
        answer_list.append(answer[share])
        answer.remove(answer[share])
        k = remainder
    return answer_list

n명을 총 줄세우는 방법은 n!입니다. 예를 들어서 위와 같은 3명을 줄을 세우면 3!가지가 전체 줄을 서는 경우의 수입니다. 잘 살펴보면, 각 사람들이 첫 번째에 있을 경우 2가지입니다.(1번 사람이 첫 번째에 있을 경우 2가지, 2번 사람이 첫 번째에 있을 경우 2가지, 3번 사람이 첫 번째에 있을 경우 2가지) 이를 수식으로 살펴보면 각 사람이 첫 번째에 올 경우의 수는 (n-1)!과 같습니다. 이것을 이용하여 한자리씩 구해나가면 됩니다! 따라서 k를 (n-1)!로 나누면, k번째 방법에 어떤 수가 가장 앞에 있는지 알 수 있습니다. 나눈 몫은 숫자를 구하는데 사용하고, 나머지는 반복문을 통해 다음 숫자를 찾는데 사용합니다. 다음 수는 remainder 나누기 ((n-1)-1)!를 하시면 됩니다! 이렇게 마지막 자리수까지 계속 반복하시면 됩니다!

출처: http://blog.naver.com/PostView.nhn?blogId=jaeyoon_95&logNo=221781918942&parentCategoryNo=&categoryNo=28&viewDate=&isShowPopularPosts=true&from=search