[Programmers] 프로그래머스 파이썬 > 줄 서는 방법

문제. 프로그래머스 줄 서는 방법

---

문제 설명

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

 

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

---

입출력 예

n	k	result
3	5	[3,1,2]

 

출처 : 프로그래머스 줄 서는 방법

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

---

나의 풀이 in Python

#[Programmers] 프로그래머스 파이썬 > 줄 서는 방법
# permutations를 활용한 풀이 - 실패
'''
from itertools import permutations
def solution(n, k):
    nl = [i for i in range(1,n+1)]
    return list(permutations(nl,n))[k-1]
'''

# 예시 : factorial 활용
from math import factorial
def solution(n, k):
    answer = []
    nl = list(range(1,n+1))
    while n!=0 :
        fact = factorial(n-1)
        answer.append(nl.pop((k-1)//fact))
        n -= 1
        k %= fact
    return answer

 

풀이 설명

1. 파이썬 모듈 permutations를 활용하면 시간 초과로 인한 실패.

2. 자동으로 factorial를 계산해주는 factorial 모듈을 활용하여 수학적으로 계산

3. k-1를 나눈 몫과 k를 나눈 나머지를 반복문마다 갱신해줌으로써 k번째 순서의 줄 서기 리스트 answer 완성

 

수학적인 예시를 통해 풀면 간단하게 해결할 수 있는 난이도의 문제였습니다.