문제

프로그래머스 - 줄 서는 방법
🚦 문제 링크입니다! 🚦

문제 풀이

접근

먼저 가능한 경우를 나열하면서 문제에서 나타나는 패턴을 파악하고자 했습니다.
첫번째 자리 숫자를 정하는 과정을 반복하면 될 것 같습니다.

n=4, k=8인 경우를 예로 들어보겠습니다. 숫자는 줄 서는 방법이고 괄호 안의 숫자는 방법의 순서 입니다.
1,2,3,4(1)
1,2,4,3(2)
1,3,2,4(3)
1,3,4,2(4)
1,4,2,3(5)
1,4,3,2(6)
2,1,3,4(7)
2,1,4,3(8)
2,3,1,4(9)
2,3,4,1(10)
2,4,1,3(11)
2,4,3,1(12)
3,1,3,4(13)
...

이런 식으로 나열됩니다.
1~6 / 7~12 / 13~18 / 19~24 구간에서 첫 번째 숫자가 각각 1,2,3,4로 정해집니다.
나열된 숫자들을 살펴보면 첫 번째 숫자가 정해진 다음, 나머지 3개의 숫자들은 n=3인 경우처럼 보입니다.
사실 그렇게 보이는 게 아니고 그게 맞습니다.
따라서 우리는 맨 처음 숫자를 정하고, n을 하나 뺀 다음 그 안에서 또 맨 처음 숫자를 정하고...를 반복하면 됩니다.

n은 알겠습니다. 그런데 k는 어떻게 해야할까요?
위의 예제에서 k=8입니다. 이 숫자로 첫번째 숫자가 2인 것을 알았습니다.
이제 우리는 2를 제외한 1,3,4로 다시 첫번째 숫자를 찾아야하는데요.
2,1,3,4(7) / 2,1,4,3(8) / ...
이렇게 2가 첫번째로 오는 애들 중 8이 두번째 경우라는 것을 알 수 있습니다.
사람을 사전 순으로 나열했기 때문에 믿고 내 숫자가 제일 처음 온 경우가 1번으로 오게 자르면 됩니다.
각 숫자가 맨 처음 올 수 있는 경우의 수는 (n-1)!입니다.
현재 n=4이기 때문에 각 숫자가 처음 오는 경우는 3!=6이죠.
그러므로 우리는 k를 (n-1)!로 잘라서 다음 사이클에서 감쪽같이 속게 만들 수 있습니다.

첫번째 자리 숫자를 정하는 과정을 일반화를 해보니 다음과 같은 규칙이 나왔습니다.
숫자 1은 k가 0(n-1)!+1 ~ 1(n-1)!일때 첫번째 자리를 꿰찬다.
숫자 2는 k가 1(n-1)!+1 ~ 2(n-1)!일때 첫번째 자리를 꿰찬다.
숫자 3는 k가 2(n-1)!+1 ~ 3(n-1)!일때 첫번째 자리를 꿰찬다.
n = n-1, k = k%(n-1)!
여기에서 숫자 123은 실제 숫자가 아니라 숫자 pool 중 작은 순서입니다.

시나리오
1. 1~n까지의 숫자가 담긴 array를 생성한다.
2. 첫번째 자리 숫자를 정하고, 해당 숫자를 array에서 pop해서 answer에 append한다.
3. 총 인원 n을 하나 감소시키고, 방법 k를 (n-1)!로 나눈 나머지로 만들어준다.
4. 위의 과정을 n이 0이 될 때까지 반복한다.

이 시나리오를 코드로 작성하면 다음과 같습니다.

import math
def find_first(n, k):
	# k가 0인 경우는 나열 방법 중 마지막 순서라는 것이다.
    if k == 0: 
        k = math.factorial(n)
    return (k-1) // math.factorial(n-1)
    
def solution(n, k):
    answer = []
    nums = [i for i in range(1, n+1)]
    
    while n > 0:
        idx = find_first(n, k)
        k %= math.factorial(n-1)
        n -= 1
    
    return answer

리팩토링

위의 코드로 정답 처리를 받고 내가 생각한 아이디어가 틀리지 않았다는 것을 확인했습니다.
이제 내 생각을 줄줄이 코드로 구현한 것에서 정리된 코드로 바꿔보겠습니다.

1) 없어도 돌아가는 코드를 삭제한다.

# k가 0인 경우는 나열 방법 중 마지막 순서라는 것이다.
if k == 0: 
    k = math.factorial(n)
return (k-1) // math.factorial(n-1)

천천히 살펴보니 위의 코드에서 k가 0일 때 예외처리를 하지 않아도 되더군요.
k가 0이더라도 k-1 = -1, return값은 -1이 되면서 index가 맨 마지막으로 인식되기 때문입니다.
굿이네요.

2) 효율적으로 인라인으로 만들 수 있는 것은 줄인다.

• find_first라는 함수가 구상하는 단계에서는 따로 함수로 만들어주는 게 나을 거라고 생각했는데, 인라인으로 만들어도 가독성에 큰 문제는 없을 것 같습니다.
• while문에서 n과 k를 따로 update했는데, 한 줄로 줄이는 것이 효율적일 것 같습니다.

3) 다르게 구현할 수 있는 부분을 주석으로 추가한다.
1~n의 숫자를 list comprehension으로 했는데, range를 활용해서 더 간단하게 만들 수도 있습니다.

리팩토링까지 마친 최종 코드는 다음과 같습니다.

소스 코드

import math
def solution(n, k):
    answer = []
    nums = [i for i in range(1, n+1)]
    # nums = list(range(1,n+1))
    
    while n > 0:
        answer.append(nums.pop((k-1) // math.factorial(n-1)))
        n, k = n-1, k%math.factorial(n-1)
    
    return answer