프로그래머스)줄 서는 방법-python

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

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

 

 

처음엔 단지 조합을 짜 k번째에 있는 것을 return하면 된다고 생각했다.

from itertools import permutations

def solution(n, k):
    answer = []
    arr = [i for i in range(1,n+1)]
    # p = permutations(arr, len(arr))
    
    a = 1
    for i in permutations(arr, len(arr)):
        if a == k:
            return(list(i))
        a+=1
    return answer

하지만 테스트케이스는 모두 통과했지만 모두 시간초과로 효율성에서 통과하지 못했다.

 

고민끝에 검색을 했다.

import math

def solution(n, k):
    lst = [x for x in range(1, n+1)]
    answer = []
    k -= 1
    
    for i in range(n, 0, -1):
        max_num = math.factorial(n)
        split_num = max_num // n
        answer.append(lst[k//split_num])
        lst.pop(k//split_num)
        k %= split_num
        n -= 1
    return answer

https://dev-dain.tistory.com/205

[Python3] 프로그래머스 lv2. 12936 줄 서는 방법

이쪽 블로그를 참고했다. 이해하기엔 10분정도 걸렸지만 깔끔하게 정리되어있다.

 

핵심은 n! // n이다

문제 예시로 설명하자면 n!은 6이다.

n!을 n으로 나누면 6 // 3 == 2,

즉 1,2,3으로 짤 수 있는 조합에서 1번과 2번의 첫번째는 1로 시작한다.

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

그리고 2번부터 4번까지는 2로 시작하고, 4번부터 6번까지는 3.

 

위 블로그에서 예시를 들어준 것처럼 만일 n이 4라고 생각해보자 

n!은 24, n!// n = 6

즉 사전 순서대로 조합을 짤 경우 6번까지는 1이 첫번째, 그 다음 6개는 2가 첫번째 그 다음 6개는 3이 첫번째.... 가 된다.

이러한 규칙으로 코드를 짠 것이다.

 

다시 문제예시처럼 n이 3인 경우로 코드를 보자.

첫번째 반복문에선 max_num(6)과 split_num(2)을 구한다.

짤 수 있는 조합은 6개이고 그 중 앞에 2개는 1이 첫번째로 오는 경우라는 뜻이다. 즉 [1,2,3],[1,3,2]

하지만 우린 k번째에 있는 조합을 짤 것이니 k//split_num을 해준다.

그리고 그것을 answer에 append시켜준다.

처음 k를 -1해준 이유는 인덱스는 0부터 시작하기 때문이다.