줄 서는 방법

이현빈·2021년 7월 26일
0

문제

프로그래머스 줄 서는 방법

문제풀이

먼저 단순히 순열로 모든 조합을 다 찾고 그 중 k번째 수를 찾는 것은 n이 최대 20이기 때문에 총 20!20!의 경우의 수가 발생해 효율성 테스트를 통과하지 못한다.

이를 해결하고자 backtracking으로 가지치기를 해보았지만 이 역시 효율성 테스트를 통과하지 못했다.

다시 문제를 읽어보니 수학적 사고력을 요하는 문제라는 것을 알 수 있었다. 힌트는 "사람을 나열 하는 방법을 사전 순으로 나열 했을 때" 란 말이었다.
사전 순으로 나열했기 때문에 (k1)(n1)!\frac{(k-1)}{(n-1)!}의 몫은 [1,2,3,...,n][1,2,3,...,n] 배열의 index가 된다. 이 때 kk가 아니라 (k1)(k-1)을 하는 이유는 배열의 index값이 0부터 시작하는 것에 맞추기 위한 기믹이다.

몫이 정해지면 kk값을 위 식에서 나온 나머지로 갱신해 nn이 0이 될때까지 반복해주면 답을 구할 수 있다.

예를 들어, k=5,n=3k=5, n=3이라 하면 몫은 22가 되고 answer배열의 첫번째 자리수는 [1,2,3][1,2,3] 배열의 2번째 index에 해당하는 값 3으로 정해진다. 값이 정해지면 3을 기존 배열에서 제거하여 [1,2][1,2]로 만들고 kk값을 나머지인 00으로 갱신하고 이 과정을 반복한다.

def solution(n:int, k: int) -> list:
    """[summary]

    Args:
        n (int): the number of all people
        k (int): kth case

    Returns:
        list: [description]
    """
    answer = [0] * n
    c = [x for x in range(1, n+1)]
    
    def factorial(N):
        res = 1
        for i in range(1, N+1):
            res *= i
        
        return res

    answer_idx = 0
    k -= 1
    while n > 0:
        num = factorial(n-1)
        idx = k // num
        k = k % num
        answer[answer_idx] = c.pop(idx)
        answer_idx += 1
        n -= 1

    return answer
profile
익숙해질때까지 한걸음씩

0개의 댓글