[프로그래머스 Lv.2] 줄 서는 방법 / 코드 상세 설명

문제

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 함수를 완성해주세요.

 

코드

def factorial(n):
    if n == 1 or n == 0:
        return 1
    return n * factorial(n-1)

def solution(n, k):
    numbers = list(range(1, n+1))
    answer = []
    k -= 1
    
    while n > 0:
        basis = factorial(n-1)
        answer.append(numbers.pop(k // basis))
        k %= basis
        n -= 1
    
    return answer

 

해설

당연히 처음엔 permutations을 쓰고 풀었다.

다 풀고 채점해보니 이 문제에는 '효율성 검사' 라는 항목이 있었다..!

너무 쉽게 설계한 코드인 만큼... 효율성은 그닥 좋지 않았다.

그 다음에 생각해낸 것이 바로 위에 적혀있는 코드이다.

 

문제 해설을 위해 임의로 n=4, k=7로 두고 문제를 풀어보겠다.

일단 맨 처음엔 k를 인덱스로 사용하기 위해 1을 빼주고 시작한다.

n이 4인 경우엔 k는 0부터 (n-1)! - 1 까지의 값을 가질 수 있다.

 

각 순번에 맞는 조합수를 세로로 적어준 것이다.

예를들어, k = 0 일 때는 가장 작은 수부터 적어준 [1,2,3,4] 가 정답이 된다.

 

첫번째 배열을 보자. 

색깔이 다른 크기가 6인 배열들이 4개가 있다.

4개의 배열들의 시작 인덱스를 보면 0, 6, 12, 18이다.

이걸 어떻게 사용하면 좋을까?

 

k를 (n-1)!으로 나눠보면 몫이 위와 같이 0, 1, 2, 3이 나온다.

우리가 찾고싶은 건 k = 7일 때의 숫자 조합이다.

 

위의 연산식의 결과를 배열 numbers에서의 인덱스로 쓰면된다.

그래서 numbers.pop(k // basis)로 인덱스 1번에 해당하는 2를 먼저 answer에 추가해주는 것이다.

 

현상황은 이렇다.

우리가 원하는 다음 탐색범위는 빨간색으로 네모친 부분이다.

 

n과 k 값을 수정해줘야 한다.

당연히 반복할수록 numbers에서 뺄 수 있는 숫자의 개수가 1씩 줄어들 것으로 n -= 1 해주면 된다.

 

그렇다면 k는 어떻게 할까?

 

우리가 보고싶은 배열의 크기는 6이므로, k를 0부터 5까지의 수로 바꿔주고 싶다.

6 -> 0

7 -> 1

8 -> 2

9 -> 3

10 -> 4

11 -> 5 처럼 말이다.

몫 연산자를 사용해서 k  %= basis 해주면 된다!

 

그 다음 과정도 살펴보자.

여기서도 동일하게 각 원소들이 (n-1)!개 존재한다.

이제 k을 (n-1)!으로 나눈 몫을 계산해보자.

 

 원본 k=7에 해당하는 몫은 0에 해당된다.

 

따라서 배열 numbers의 0번째 원소를 answer로 옮겨준다.

그 후 k와 n도 값을 바꿔준다.

 

그렇다면 세번째 반복문은 위와 같은 상태로 시작하게 된다.

 

마지막 네번째 반복문은 위와 같은 상태로 시작하게 된다.

 

n이 0이 되면, 즉 더이상 numbers에서 꺼낼 원소가 없다면 반복문은 종료된다.

위의 과정을 거쳐 답은 [2, 1, 4, 3]이 된다!

 

효율성 검사도 무사히 통과할 수 있었다. ☺️