[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]

입출력 예시 설명

입출력 예 #1 문제의 예시와 같습니다.

문제 풀이

# 몫과 나머지

풀이 과정

n개의 수로 만들 수 있는 조합들 중 k번째 조합이 무엇인지 알아내는 문제입니다.

이 문제를 n개의 수로 만들 수 있는 조합을 먼저 구하고, k번째 수를 return하면 당연히 시간 초과가 나게 됩니다.

따라서 이 문제는 모든 조합을 먼저 구하는 것이 아니라, 규칙을 찾아서 풀어야 합니다.

nums = [1,2,3]이라면, 맨 앞에 1이 왔을 때 2!, 2가 왔을 때 2!, 3이 왔을 때 2!의 조합의 수가 만들어집니다. 즉, 3개의 수로 5번째 조합을 구한다면, (5-1) // (3-1)!을 함으로써 현재 자리에 몇번째 수가 와야 할 지 알 수 있습니다.

k // (n-1)!이 아니라 (k-1) // (n-1)!이 되어야 하는 이유는 다음과 같습니다.

만약 k=4라면 정답은 [2,3,1]이 되어야 하는데, k // (n-1)!을 사용한다면 4를 2!으로 나눈 몫이 2이기 때문에 [3,1,2]라는 답을 내놓게 됩니다. 그리고 다음 k는 k % (n-1)!으로 구합니다.

또, 앞에서 나온 수는 뒤에서 나올 수 없기 때문에, nums 리스트에서 pop해주도록 합니다.

몫과 나머지를 이용하는 푸는 문제는 많은 문제가 있는데, 이런 유형의 문제들은 항상 1의 차이가 큰 차이를 불러오기 때문에 숫자에 유의하여야 합니다.

전체 코드

1번 풀이: 내 풀이

def solution(n, k):
    nums = [i for i in range(1,n+1)]
    ans = []
    k, i, s = k-1, 1, n-1
    for j in range(2,n): i *= j
    while True:
        q, k = divmod(k, i)
        ans.append(nums[q])
        nums.pop(q)
        if len(ans) == n: return ans
        i, s = i//s, s-1

2번 풀이: 정석 풀이

def setAlign(n, k):
    from math import factorial
    answer = []
    order = list(range(1,n+1))
    while n:
        fact = factorial(n-1)
        answer.append(order.pop((k-1)//fact))
        n,k = n-1, k%fact
    return answer