[Python] 프로그래머스 - 줄 서는 방법

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

풀이

제한 사항으로 인해, 단순히 전체 경우의 수를 모두 구한 뒤에, 그 중에서 k번째 경우를 출력하는 것은 불가능하다.

 

줄 세우는 방법에 대해 구할 수 있는 방법을 생각해보면, Permutation(순열)을 떠올릴 수 있다.

그리고 문제에서 줄을 세우는 방식은 주어진 예시와 같이, 가장 낮은 번호부터 시작해 가능한 경우의 수를 모두 세우고, 그 다음 번호로 넘어가는 방식이다.

예시1

주어진 예시인 n=3인 경우에

가장 먼저 1로부터 시작해 줄을 세우는 방법으로 시작해, 나머지 두개의 수를 앞이 앞이 작은 순서대로 세우게 된다.

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

그 다음으로는 2로 시작해, 다음과 같은 순서로 줄을 세우게 되고

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

마지막으로는 3으로 시작해, 다음의 순서로 모든 경우의 수를 구할 수 있다.

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

그리고 k=5, 즉 5번째로 줄을 세우는 방법을 구해야 하므로 정답은 [3,1,2]가 된다.

 

여기서 생각해야할 것은 전체 경우의 수를 구하지 않고 어떻게 k번째에 오는 방법을 구할 수 있는지인데,

위의 예시를 곰곰이 살펴보면 1, 2, 3으로 시작하는 경우 모두 각각 2개씩의 경우의 수가 나타나는 것을 알 수 있고,

맨 앞에 오는 수를 고정해놓고 나머지 수만을 사용해 순열을 구하면 2! = 2의 값을 구할 수 있다.

 

이를 활용해 k=5인 경우를 재해석해보면, k = 5 = 2! x 2 + 1의 값으로 분해할 수 있고,

이는 맨 앞에 오는 수를 2개 거치고 난 뒤에, 3번째로 맨 앞에 오는 수에서 만들어 질 수 있는 경우의 수에서 첫번째 경우의 수를 선택하라는 것으로 해석할 수 있다.

 

즉, [1,2,3]중에서 3으로 시작하는 전체 줄서기 방법 2가지 중에서 첫번째 방법을 선택하면 되는 것이다.

 

추가적으로, 만약 k = 4 = 2! x 2 + 0처럼 나머지 값이 0이라면, 두번째 수인 2로 시작하는 전체 줄 세우기 방법 중에서 마지막 방법인

[2,3,1]이 정답이 될 것이다.

예시2

동일한 방법으로 n=10, k=100인 경우를 살펴보자.

 

k = 100 = 4! x 4 + 4 인 경우에, 가장 큰 factorial값으로 나눠질 수 있다.

즉, 끝의 4명을 줄 세우는 순열을 4번 돌리고, 그 다음 순열의 4번째 순서가 정답이 되는 것이다.

 

그러므로 1~5까지는 그대로이고, 그 다음에 위치할 수는 사용 가능한 수(6,7,8,9,10)에서 5번째 수인 10이 오게된다.

(4번 돌리고 5번째 수에서 4번째 순서)

 

그리고 나머지인 4를 다시 fatorial값으로 분해하면 4 = 2! x 2 + 0 이므로, 끝에서 3번째 자리까지만 변화하고 나머지는 변하지 않는다.

따라서 사용가능한 수인 6,7,8,9 중에서 6은 고정이고 나머지 7,8,9 중에서 2명을 사용해 2번 돌리는 마지막 경우가 선택되므로

8,9,7이 마지막 순서가 된다.

 

최종적으로는 [1,2,3,4,5,10,6,8,9,7]이 정답이 된다.

 

이 규칙을 이용해 알고리즘을 작성하게 되면, 다음과 같은 방식으로 알고리즘을 구상할 수 있다.

1. n!과 k를 비교
   • n>k인 경우
     • 더 적은 수의 인원만 움직여도 k를 달성할 수 있으므로, 앞 순서의 사람은 움직일 필요가 없음 -> 그대로 세움
   • n<=k인 경우
     
     • k / n!의 몫, 나머지를 계산
       • 몫 : n!의 방법으로 몇차례 돌려야 하는지
       • 나머지 : 그 이후에 몇번째 경우를 선택해야 하는지
2. n = n-1 & k = k%n!
3. n이 0이 될때까지 반복

나의 풀이

def solution2(n, k):
    from math import factorial
    from itertools import permutations
    answer = []
    nums = list(range(1,n+1))
    # n-1명을 세우는 경우의 수
    f = n
    while k>1 and f>0:
        if k >= factorial(f):
            div, k = divmod(k,factorial(f))
            nums = sorted(list(set(nums)-set(answer)))
            # 고정 자리수 추가(움직이지 않는 사람)
            tmp = len(nums)-(f+1)
            if tmp<0:
                a = []
            else:
                a = nums[:tmp]
            answer += a
            nums = sorted(list(set(nums)-set(answer)))
            # div,k에 따라 변화하는 숫자 추가(돌리는 사람)
            if nums:
                if k>0:
                    answer.append(nums[div])
                else:
                    answer.append(nums[div-1])
                nums = sorted(list(set(nums)-set(answer)))
            else:
                break
            
        f-=1
        
    perms = list(permutations(nums,len(nums)))
    answer+=perms[k-1]
    
    return answer

풀이 2

def solution(n,k):
    from math import factorial
    answer = []
    nums = list(range(1,n+1))
    while n>0:
        div,k = divmod(k, factorial(n-1))
        if div:
            if k:
                answer.append(nums.pop(div))
            else:
                answer.append(nums.pop(div-1))
                
        else:
            if k:
                answer.append(nums.pop(0))
            else:
                answer.append(nums.pop(-1))
        n-=1
            
    return answer

 

기본적으로 동일한 원리의 알고리즘이지만, 풀이2의 경우가 조금 더 깔끔한 풀이라고 생각한다.