[프로그래머스💯] 코딩테스트 연습 > 연습문제 > 줄 서는 방법 / Python 문제풀이

 

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

import copy


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


def solution(num, k):

    if num == 1:
        return [num]

    remain_nums = [i for i in range(1, num+1)]

    cands = [factorial(i) for i in range(num-1, 0, -1)]  # 팩토리얼 큰 것 부터 모음
    pre_nums = []  # 각 자리를 결정해주는 수
    '''
    만약 pre_nums = [1,1,1] 이면 정답 = [2,3,4]
    '''

    k_copy = k  # 2번째 방법 때 k 써야돼서
    for i in range(num-1):
        pre_nums.append(((k_copy-1) // cands[i]))
        k_copy = k_copy % cands[i]
    pre_nums.append(k_copy)

    result = []

    for i, v in enumerate(pre_nums):
        num = remain_nums.pop(remain_nums.index(remain_nums[v]))
        result.append(num)
        if v == -1:
            result.extend(reversed(remain_nums))
            break

    return result

 

 

풀이)

처음엔 DFS 로 직접 돌린 뒤 k 번째 때 리턴하는 방식으로 짰는데 시간초과가 뜨더군요..

곰곰이 생각하다가 꼭 루프를 안돌리고 수학적으로 계산해내는 방법을 찾아냈습니다.

 

 

n 명이 줄 서는 방법은 총 n! 가지 수 입니다.

n-1 명이 줄 서는 방법은 (n-1)! 가지 수 이구요.

 

이러한 특성을 이용해서  맨 앞 사람 뒤에 줄 서는 사람들의 가짓 수를 미리 계산할 수 있습니다.

n = 4 , k = 15 이라면

 

1 , 2 , 3 , 4

1 , 2 , 4 , 3

1 , 3 , 2 , 4

이런식으로 진행되겠죠? 그러면 3! = 6 인것을 이용해서

2, 1, 3, 4 는 k=7 일 때라는 것을 알 수 있습니다.

즉, 3! 으로 나눈 몫은 맨 앞 사람이 몇번의 사람인가를 결정해줍니다!

그리고 3! 으로 나눈 나머지를 다시 2! 으로 나눠 이제 2번째 사람이 몇 번째 사람인지도 결정해 줄 수 있습니다.

 

이를 이용해

15 / (3!) = 2 ... 3       =>       k=15 의 첫 사람은 1+2 = 3 이다.

-> 3 이 남음

3 / (2!) = 1 ... 1        =>       두 번째 사람은 [1,2,4] 중  (1+1) 번째 인 2이다.

-> 1 이남음

남은 [1, 4]  중 1 번째 이다.  따라서 , [3,2,1,4]

 

이 방식을 코드로 구현하면 됩니다.

저는 cands 라는 리스트에 필요한 팩토리얼들을 미리 계산해주었고, 

pre_nums 에 팩토리얼의 몫들을 넣은 뒤, 위와 같은 계산을 통해 구할 수 있었습니다. 😁

 

 

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges