프로그래머스 줄 서는 방법 (python, 파이썬)

• 문제 설명

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]

---

• 코드

def factorial(n):
    v = 1
    for i in range(1, n+1):
        v *= i
    return v

def solution(n, k):
    answer = []
    lst = [x for x in range(1, n+1)]
    
    while lst:
        temp = factorial(n-1)
        q, r = divmod(k, temp)
        q = q-1 if r == 0 else q
        
        answer.append(lst.pop(q))
        
        n -= 1
        k = r
        
    return answer

앞에서부터 answer의 배열을 채워주는것이다. python에 있는 permutation순열을 사용하니까 바로 시간초과가 떴다. 

level3문제가 이렇게 쉽게 나올리가없지 하는 생각이 들었다.

 

n=3, k=5을 가정하면

 

맨 처음 숫자로 올 수 있는 숫자는 1, 2, 3이다.

그리고 1,2,3일때 뒤에 올 수 있는 경우의수는 2!(=n-1!)이다. 나눗셈을 통해 몫으로 큰 순서를 잡아 나가는 것이다.

k=5를 2!으로 나누어주면 몫이 2, 나머지가 1이다.

몫이 의미하는것은 index 2번째(python은 0부터 시작하니 직관적으로는 3번째) 값의 숫자가 와야한다는 뜻이다.

 

그리고 첫번째 숫자가 결정되었기 때문에 그다음 1,2 뒤에 올수있는 경우는 1!이다. n을 1감소시키는것이다

그리고 k번째는 나머지 r번째이기 때문에 줄여준다.

 

lst값을 다 쓸때까지 while문으로 반복해준다.

---

• 출처

programmers.co.kr/learn/courses/30/lessons/12936?language=python3