[알고리즘] 프로그래머스 Lv2 줄 서는 방법

문제

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

풀이과정

문제는 정말 간단하다.
1부터 n 까지의 수를 나열하는 방법 중 사전 순으로 나열 했을 때, k번째 나열된 순서를 반환하는 함수를 작성하면 된다.

가장 간단한 풀이는 아래와 같이 itertools의 permutations 함수를 써서 정렬하고 k번째에 위치한 값을 반환하는 것이라 생각한다.

from itertools import permutations as perm

def solution(n, k):
    lst = sorted(list(perm(range(1,n+1), n)))
    return list(lst[k-1])

그러나 이 방법을 사용하면 시간 초과가 난다.

그래서 k번째를 바로 구할 수 있는 방법은 없을까 고민했다.
어렴풋이 생각은 나는데 그것을 정리하고 코드로 작성하는 과정이 쉽지는 않았다.

먼저, 제일 앞자리에 대해서 생각해본다.
n이 3인 경우, 1XX, 2XX, 3XX 이렇게 될 수 있는데 각각 뒤에 2! 개의 경우의 수가 존재한다.
n이 4인 경우에는 1XXX, 2XXX, 3XXX, 4XXX 이렇게 될 수 있고 각각 뒤에 3! 개의 경우의 수가 존재한다.

그렇다면 n=4, k=10인 경우에 대해서 생각해보자.
1XXX : 1 - 6번째
2XXX : 7 - 12번째
3XXX : 13 - 18번째
4XXX : 19 - 24번째
이므로 k번째 수는 2XXX이 될 것이다.
두번째 수는
21XX : 7 - 8번째
23XX : 9 - 10번째
24XX : 11 - 12번째
이므로 k번째 수는 23XX이 되고 23XX 의 두 가지 경우 중 사전 순으로 정렬했을 때 뒤에 있는 수가 될 것이다.

이 로직을 팩토리얼과 while 반복문, if 조건문을 사용하여 구현하였다.

코드

import math

def solution(n, k):
    answer = []
    org = list(range(1, n+1))
    idx = 1
    # i = 0
    while k > 0:
        # print(i, '번째:', n, k, idx, org, answer) # 디버깅용 코드
        if k - idx * math.factorial(n-1) > 0:
            idx += 1
        elif k - idx * math.factorial(n-1) < 0:
            k -= (idx-1) * math.factorial(n-1)
            tmp = org[idx-1]
            answer.append(tmp)
            org.remove(tmp)
            idx = 1
            n -= 1
        else:
            tmp = org[idx-1]
            answer.append(tmp)
            org.remove(tmp)
            answer.extend(sorted(org, reverse=True))
            break
    # i+=1
    return answer

다른 사람의 풀이

def solution(n, k):
    from math import factorial
    answer = []
    order = list(range(1,n+1))
    while n!=0 :
        fact = factorial(n-1)
        answer.append(order.pop((k-1)//fact))
        n,k = n-1, k%fact
    return answer

유사한 로직이지만 훨씬 깔끔하다.
(k-1)//fact 부분과 k = k%fact으로 처리하는 부분이 인상 깊다.