[코딩테스트] 프로그래머스 - 줄 서는 방법 (Lv.3) in Python

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다.

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

 

예시:

n = 3, k = 5.

 

n = 3명이 줄 서는 경우의 수는

1. [1, 2, 3]
2. [1, 3, 2]
3. [2, 1, 3]
4. [2, 3, 1]
5. [3, 1, 2]
6. [3, 2, 1]

여기서 k = 5번째 경우는 [3, 1, 2].

따라서 정답은 [3, 1, 2]가 된다.

 

 

자세한 설명 -programmers.co.kr/learn/courses/30/lessons/12936 

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

 

 

풀이

1. 무식한 방법

- 처음엔 무식하게! 그러나 간단하게 풀어보려 했다.

from itertools import permutations
def solution(n, k):
	baseArr = [x for x in range(1,n+1)]
	arr = list(permutations(baseArr, n))
    
    answer =  list(arr[k-1]) 
    return answer

 

- 하지만 이는 효용성 테스트를 통과하지 못했다 ㅠ

- n이 20 이하로 주어지고,

- 따라서 permutations의 개수는 최악의 경우 n! = 20! = 2,432,902,008,176,640,000... 세기도 어렵다그니까...음... 사실 세지도 못하겠다! 암튼 1억은 훌쩍 넘어가는 수가 되버린다!!! (영어로는 2 quintillion 어쩌구가 된다고 한다. 이런 단어 난생 처음 들어본당!)

- 그러므로 모든 permutations의 경우의 수를 따져보는 것이 아니라, 주어진 n과 k에서 규칙을 도출해서 바로 바로 answer 배열을 채워줘야 되겠다.

 

2. 덜 무식한 방법

- 보니까, 규칙이 보였다.

- 만약 n = 4이라면,

처음 6개 - (n-1)! = (4-1)! = 3! = 6 - 의 경우는 1로 시작하고, 다음 6개의 경우는 2로 시작하고, ... 이런 패턴이 보인다.

처음 6개의 경우 중에서도, 처음 2개 - (n-2)! = (4-2)! = 2! = 2 - 의 경우는 1을 제외한 나머지 수들 중 처음 있던 숫자로 시작한다.

처음 6개 경우 중에, 처음 2개 경우 중에, 처음 1개 -  (n-3)! = (4-3)! = 1! = 1 - 의 경우는 1, 2를 제외한 나머지 수들 중 처음 있던 숫자로 시작한다.

 

이런 패턴으로 봤을 때, 풀이를 다음과 같이 구성할 수 있다.

 

 

 

파이썬 구현 

import math
def solution(n, k):
    nums = [x for x in range(1,n+1)]
    answer = []
    
    while n > 0:
        n -= 1
        q, r = divmod(k, math.factorial(n)) # Step 1
        if r == 0: # Step 2
            q -= 1
        
        curr = nums[q]
        answer.append(curr) # Step 3
        nums.remove(curr) # Step 4
        k = r # Step 5
    return answer

Step 1

- k를 (n-i)!로 나눈 몫과 나머지를 저장

 

Step 2

- 나머지가 0이라면 - 예를 들어 n=3, k=2일 때, 처음 루프의 경우 - 몫에서 1을 빼준다. index는 0부터 시작하기 때문

 

Step 3

- 남은 수들 중에 q번째 있는 수를 answer에 붙여줌

 

Step 4

- 방금 answer에 붙여준 수를 후보 숫자 배열에서 없애줌

 

Step 5

- k를 나머지로 설정하고 - "몇 번째 그룹" 안에서 또 몇 번째 위치에 있는 지를 탐색해야 하므로 - 루프 다시 돔

 

 

Step 2에서 조금 헷갈렸다.

이렇게 풀면, 가능한 모든 permutations의 경우를 배열로 만들어 줄 필요 없이, 하나의 배열만 만들어내면 되니 효용성 테스트도 넘어갈 수 있겠다.