📗 줄 서는 방법

프로그래머스

def solution(n, k):
    def factorial(n):
        if n <= 1:
            return 1
        return n * factorial(n-1)
    
    numbers = list(range(1, n+1))
    k -= 1
    answer = []
    
    for i in range(n, 0, -1):
        fact = factorial(i-1)
        index = k // fact
        k %= fact
        
        answer.append(numbers[index])
        numbers.pop(index)
    
    return answer

• 조건에 맞는 순열을 permutations 없이 구현해보는 문제였습니다.

왜 이렇게 풀었을까?

• permutations를 사용하면 너무나도 간단히 풀릴 문제라, 당연히 이 방법은 아니겠다 하는 생각에 '그렇다면 다른 방법으로 풀 수가 있나?'를 먼저 떠올려보았습니다.
• 수학적인 접근법이 필요해보였고, 이를 위해서 순열의 구조를 이해하고 그 패턴을 살펴보기로 하였습니다.
• n개의 원소가 주어졌을 때, 순열의 첫 번째 원소를 선택하는 방법은 n가지이며, 그 뒤에 나오게 될 원소들을 고르는 방법은 총 (n-1)!가지가 됩니다.
• 그래서 전체 순열을 n개의 그룹으로 보았을 때, 각 그룹이 (n-1)!가지의 순열을 포함하고 있음을 알게 되었습니다.
• 그리고 k가 문제에서 주어졌기 때문에 k번째 순열이 어느 그룹에 속하는지를 알아야했고, k를 (n-1)!로 나누어 몇 번째 그룹에 속하는지, 또 그 나머지를 구하여 해당 그룹에서 몇 번째 순열인지까지 알아낼 수 있었습니다.
• 이 과정을 일반화해서 현재 자리에 올 원소의 index를 구해주고, 다음 자리를 위해 k를 갱신하는 로직으로 코드를 짜게 되었습니다.
• 말로 설명하기도 어렵고, 생각보다 로직을 떠올리기가 어려워서 여러 자료를 참고해 풀어냈던 문제이지 않았나 싶습니다.