(Python) - 프로그래머스 : 줄 서는 방법

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

코딩테스트 연습 - 줄 서는 방법

 

• 해설 :

1번부터 n번, 총 n명의 사람이 줄을 서는 모든 경우를 사전순으로 정렬한 후 k번째 줄 서는 방법을 찾는 문제이다.

 

 

 

 

• 풀이 :

처음엔 permutations을 이용하여 실제로 줄 서는 모든 방법을 찾으려고 하였으나 n의 범위가 20이므로 메모리, 시간 효율성에서 모두 통과하지 못했다. 따라서 다른 방법을 생각하였는데 이는 수학적 특징을 이용한 것이다.

 

N명의 사람을 줄 세우는 경우의 수는 N!(팩토리얼)이다. Python의 math모듈에는 마침 factorial 함수를 지원하므로 이를 사용해서 N!을 구한다. 이를 사전순으로 나열하였을 때, K를 인덱스로 나눴을 때, 그 몫이 각 자릿수마다 존재하는 N의 가짓수이다. 따라서 K를 n-1로 나눈 몫과 나머지를 이용하여 나머지가 0일때까지 진행하며 그 때의 인덱스를 기록하면 우리가 찾는 순서를  알 수 있다.

 

 

 

 

import math
def solution(n, k):
    Nums = list(range(1, n+1))
    Answer = []
    while n != 0:
        temp = math.factorial(n-1)
        Index, k = (k-1)//temp, k%temp
        Answer.append(Nums.pop(Index))
        n -= 1
    return Answer