[Programmers]Python_줄 서는 방법

문제

 

문제 설명

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! 이하의 자연수 입니다.

 

코드

import math
def solution(n, k):
    #1 ~ n까지 리스트 정의
    people = [i for i in range(1, n + 1)]
    result = []
    #끝나는 지점 정의
    end_point = n
    
    while True:
        #n명일때 줄을 서는 방법은 n!이다
        f = math.factorial(n - 1)
        #몫은 해당 인덱스에 있는 값을 가르키고 나머지는 f의 마지막 값인지 아닌지 판단해준다
        q, r = divmod(k, f)
        k = r
        
        if r == 0:
            result.append(people.pop(q - 1))
        else:
            result.append(people.pop(q))
            
        n -= 1 #사람이 한 명 빠짐
        
        if len(result) == end_point:
            return result

 

진행 과정

예제 #1

n = 3

k = 5

 

문제를 풀기에 앞서 2명의 사람이 있을때부터 생각해보자.

2명이 있다면 줄을 서는 방법은

• [1, 2]
• [2, 1]

으로 총 2! = 2가지의 경우가 있다.

 

그리고 3명의 사람이 있다면

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

으로 총 3! = 6가지의 경우가 있다.

 

여기서 사람 1이 맨 앞에 서있을 때의 경우를 보면 

• [1, 2, 3]
• [1, 3, 2]

사람 2가 맨 앞에 서있을 때의 경우는

• [2, 1, 3]
• [2, 3, 1]

마찬가지로 사람 3이 맨 앞에 서있을 때의 경우

• [3, 1, 2]
• [3, 2, 1]

즉, 각 한 사람마다 맨 앞에 있는 경우는 2! = 2가지가 있다. 이것은 (3 - 1)!와 같다.

코드에서는 이 부분을 math.factorial(n - 1)으로 구현하였다.

 

그렇다면 이 부분을 사용하여 k번째에 누가 맨 앞에 서있는지 알아낼 수 없을까?

 

1번째에 맨 앞에 서있는 사람을 한 번 보자.

당연히 사람 1이 맨 앞에 서있겠지만 위에서 (3 - 1)!을 사용하여 어떻게 사람 1이 맨 앞에 서있는 것인지 생각해보자.

사람 1이 맨 앞에 서있을 경우는 총 2가지이다. 즉, 1번째와 2번째는 맨 앞에 사람 1이 서있다는 말이다.

그렇다면 이것을 "1 // 2 = 0, 1 % 2 = 1" 이라고 표현해두자

 

다음으로 2번째 맨 앞에 서있는 사람을 보자.

1번째와 마찬가지로 이것을 "2 // 2 = 1, 2 % 2 = 0"이라고 표현해둔다.

 

3번째 맨 앞에 서있는 사람.

"3 // 2 = 1, 3 % 2 = 1"

어? 여기서는 3 // 2의 값 1이 people의 인덱스 1에 있는 값 2로 맨 앞에 서있는 사람이 맞다.

다음으로 계속 진행해보자.

 

4번째 맨 앞에 서있는 사람.

"4 // 2 = 2, 4 % 2 = 0"

아... 여기서는 4 // 2의 값 2가 people의 인덱스 2에 있는 값 3으로 틀리다.

 

5번째 맨 앞에 서있는 사람.

"5 // 2 = 2, 5 % 2 = 1"

여기서는 또 인덱스 2에 있는 값 3으로 맞다. 이쯤되면 패턴이 어떻게 되는 것인지 얼추 알아냈을 것이다.

 

6번쨰 맨 앞에 서있는 사람.

"6 // 2 = 3, 6 % 2 = 0"

인덱스 3은 out of range 값이므로 틀리다.

 

패턴이 무엇일까??

우선 인덱스에 있는 값이 맞았을 경우를 보면 나머지가 1 이었을 경우에만 다 맞았다. 그리고 나머지가 0인 경우에는 모두 틀렸다. 또한 나머지가 0일때는 몫을 -1을 해주면 인덱스에 있는 값이 맞게된다.

 

이제 패턴은 찾았다고 할 수 있다. 코드 구현을 해보자.

• f = math.factorial(n - 1) #각 사람별 맨 앞에 서 있을 경우의 수
• q, r = divmod(k, f) #k번째와 f개의 몫과 나머지를 구한다
• if r == 0: result.append(people.pop(q - 1)) #나머지가 0일 때는 몫 - 1을 해주어야 해당 인덱스에 있는 값이 맞다
• else: result.append(people.pop(q)) #나머지가 0이 아닐때는 해당 몫의 인덱스에 있는 값이 맞다

여기까지 맨 앞에 어떤 사람이 오는지는 대충 알겠다. 그렇다면 다음 사람이 오는 것은 어떻게 알까?

간단하게 생각하자. 2명일 때 맨 앞에 오는 사람은 3명일 때 두 번째에 오는 사람과 같다.

 

n -= 1을 하여 위에서 진행한 과정을 한 번 더 반복하면 된다는 뜻이다.

 

하지만 예제 #1에서 n = 3, k = 5라고 한다면 n -= 1을 적용하여 진행했을때 5 // 2 = 2가 되어 out of range가 된다.

당연하다. 맨 앞에 사람이 정해졌으니 두 번째에 사람이 올 경우 또한 줄어든다.

 

2명이되면 맨 앞에 사람이 올 경우는 각 한 가지 경우밖에 없다는 말이다.

 

이전에 5번째 맨 앞에 있는 사람을 구할때 맨 앞에 사람 3이 올 경우 두 가지 [3, 1, 2], [3, 2, 1] 중 첫 번째 값을 가져왔다.

그러면 다음 두 번째로 서있을 사람은 몇 번째 방법을 구해야하는 것이겠는가. 그렇다! 첫 번째 방법이다.

 

두 번째에 서있을 사람은 n = 2, k = 1일 때의 방법을 찾는 것이라고 할 수 있다. 그리고 k를 어떻게 계산하여 알아낼까...

이전에 5 % 2 = 1의 값을 가져오면 된다. 값이 0이라면 두 번째의 값, 마지막 값이라고 할 수 있겠다.

 

코드 실행 과정은 다음과 같다.

 

1) f = 2, q = 2, r = 1, k = 1

2) result = [3]

 

3) f = 1, q = 1, r = 0, k = 0

4) result = [3, 1]

 

5) f = 1, q = 0, r = 0, k = 0

6) result = [3, 1, 2]