[4코1파] #65. LV 2. 줄 서는 방법

[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (65일차)
[4코1파] 2023.01.13~ (56일차)

Today :

2023.03.09 [65일차]

프로그래머스 LV 2
줄 서는 방법
https://school.programmers.co.kr/learn/courses/30/lessons/12936

문제 설명

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

입출력 예

입출력 예시 설명

입출력 예 #1
문제의 예시와 같습니다.

문제 풀이 방법

처음 시도는 itertools 모듈의 permutations으로
경우의 수를 만든 후에 sorted 해서 인덱싱해서 찾는 방법으로 시도 했는데
테스트 케이스 와 효율성 검사에서 걸림

도저히 답이 안나와서 '질문하기' 에서 소스를 얻음
이것은 팩토리얼을 이용해서 풀어야 하는 문제였다.
팩토리얼을 이용한 dp 문제 !

멋진 해설 : https://school.programmers.co.kr/questions/24730

예를 들어 줄을 세워야 하는 사람이 4명이라고 하면,
세우는 방법은 4x3x2x1 개로 4!가 나오게 되고
앞자리를 바꾸는 것은 4!(120) /4명 = '6' 이 지나면 앞자리가 바뀜
이러한 것을 기반으로 해서 몫과 나머지를 이용하고 줄을 세워야 하는 사람을 해당 인덱싱에서 pop 해서 가져오면 되는 문제!
좀 어려움 수학문제잖어..

증빙

내 코드

import math

def solution(n, k):
    k = k-1
    answer = []
    n_lst = [_ for _ in range(1,n+1)]
    
    for i in range(n,0,-1):
        div, k = divmod(k,math.factorial(i-1))
        answer.append(n_lst.pop(div))
        
    return answer

여담

경우의 수는 재밌지.. 이건 역문제도 나올 수 있을 것 같다...
줄 서는 방법은... 빨리가서 서는 거지 뭐..