[프로그래머스 - Level 3] 줄 서는 방법

lsh9672·2022년 2월 3일

programmers

목록 보기

9/13

문제

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! 이하의 자연수 입니다.

입출력 예 설명

접근(1)

순서에 상관있게 나열하는 방식이므로 처음 보자마자 순열을 이용해서 풀어보았다
순열은 permutations라이브러리를 이용했다.
1부터 n까지의 숫자로 만들수 있는 모든 조합을 뽑아내고, 그 중에서 k번째숫자를 리턴하게 했다.

당연히 완전탐색을 하니 효율성에서 시간초과가 발생했고, 정확성에서도 두개의 케이스에서 시간초과가 발생했다.

from itertools import permutations as pm


def solution(n, k):
    answer = []
    
    human_list = [i for i in range(1,n+1)]
    
    temp = list(pm(human_list,n))[k-1]

    for i in temp:
        answer.append(int(i))
    
    return answer

접근(2)

완전탐색으로 전부 구해놓고 시작하면 안된다는 것을 알고 방법을 고민했다.

그래서 생각한 방식이 모든 경우를 다 구하는게 아니라 k번째에 조금씩 근접해서 구하는 방식을 선택했다.

n명의 사람을 줄세우는 경우는 n!이다.

그렇다면 맨 앞의 사람을 고정시켜두고 나머지를 줄세우는 경우는 (n-1)!이 된다.

즉, 사람 하나를 고정시키면 (n-1)!씩 n개의 경우가 생기는 것이다.

n이 3인경우를 예를 들어보면, 맨앞을 1로 고정시켜보겠다.

그럼 [1,2,3],[1,3,2] => (n-1)! => 2개의 경우가 생기게된다.
그 다음 부터 나오는 경우의 수는 앞의 숫자만 바뀌고, 앞의 숫자에 따라서 각각 2개씩 생기는 것이다.
즉, 앞의 숫자가 1일때 2개의 경우,2일때 2개의 경우, 3일때 두개의 경우가 생긴다.

이를 n으로 바꿔보면 앞자리가 1부터 n까지 각각(n-1)!개씩 생기게 된다.

그렇다면 k번째를 구하기 위해서 앞자리가 몇인지 추측을 해야된다.
이는 k를 (n-1)!로 나누면 알수 있다.

앞자리 숫자가 1부터 n까지 각각 (n-1)!개씩 가지고 있기 때문에 k//(n-1)!을 해서 나온 값이 (n-1)!개의 뭉텅이를 몇번 지났는지가 되고, k%(n-1)! 한 값이 0이 아니라면 (n-1)!의 뭉텅이를 k//(n-1)개 만큼 지나치고 그 다음 것이라고 볼수 있고, 0이라면 'k//(n-1)'개 뭉텅이의 마지막 이라고 보면 된다.

이 또한 n을 3, k를 5로 두고 예를 들어보겠다.

(n-1)!이므로 1일때 2개, 2일때 2개 3일때 2개씩 총 6개이다.
5번째숫자를 구하고 싶으면 5//2 = 2가 되고, 이 말은 2개씩 존재하는 뭉텅이를 2개 지났다는 의미이고 ([1,2,3],[1,3,2][2,1,3],[2,3,1] 앞의 숫자를 고정해서 2개씩 존재하는 것을 2개 지남) 5%2 = 1이므로 2개를 지나서 1개만큼 더 왔다는 뜻이된다.
즉, [2,3,1]이 4번째이고 그 다음에는 5번째 순서인 [3,1,2]가 답이 된다.

이 과정들은 n번만큼 반복을 하게 된다.
코드로 보면 k//(n-1)!(코드에는 (n-1)!을 n!//n으로 표현했다.)은 맨앞에 고정할 사람이다
human_list변수에 사람을 나열해두었는데 인덱스를 0부터 시작하기 때문에 k//(n-1)!이것을 그대로 pop해주면 된다.

pop해주는 이유는 중복될수 없기 때문에 사람을 하나 쓰면 리스트에서 빠져야되기 때문이다.

다음 자리수에서 사람을 선택해야되기 때문에 k%(n-1)!이 값은 다시 k에 넣어주면 된다.

맨앞부터 n이 0이 될때 까지, 즉 모든 사람을 줄세울때까지 위에서 이야기한 과정들을 반복하면 된다.

#팩토리얼 계산 함수
def fac(num:int) -> int:

    total = 1
    for i in range(1,num+1):
        total *= i

    return total


def solution(n:int,k:int) -> list:
    answer = []

    #사람 나열
    human_list = [i for i in range(1,n+1)]
    
    while n != 0:

        #몇개씩 있는지 - 앞에 숫자를 고정했을때 몇개씩 경우가 나오는지 계산
        temp = fac(n)//n

        #앞에 고정할 사람의 순번
        passed_people = k // temp

        k = k % temp

        #나눈 나머지가 0이 아니면 k//temp만큼 지나치고 (k//temp)+1번째 사람이라는뜻
        if k != 0:
            answer.append(human_list.pop(passed_people))
        else:
            answer.append(human_list.pop(passed_people-1))
        
        n -= 1

    return answer