[프로그래머스 level3] 줄 서는 방법 Python

IT공부중·2020년 4월 10일
0

알고리즘

목록 보기
14/49

https://programmers.co.kr/learn/courses/30/lessons/12936

import math

def solution(n, k):
    answer = []
    numberList = [i for i in range(1, n+1)]
    while (n != 0):
        temp = math.factorial(n) // n # 한개에 몇개씩의 값이 있을지 알 수 잇음.
        index = k // temp
        k = k % temp
        if k == 0:
            answer.append(numberList.pop(index-1))
        else :
             answer.append(numberList.pop(index))

        n -= 1
    
    return answer

ex) n = 3, k = 5 일 때
문제에 예시에 있듯이 [1,2,3] 이라는 사람들이 있으면 줄 설 수 있는 방법은 3 x 2 x 1로 6개이다. 이는 팩토리얼로 구할 수 있다. python의 math에는 factorial 함수가 들어있다.
거기에 현재의 숫자를 나누면 각 숫자가 첫번째에 왔을 때 몇 번의 방법이 있는지 알 수 있다. 6 // 3을 하면 2가 된다. 즉, [1,2,3][1,3,2] [2,1,3][2,3,1] [3,1,2][3,2,1]로 각 숫자당 2개의 방법이 생긴다.

index는 우리가 신경써야할 기준이라 볼 수 있다. k번째를 구해야하니 k // temp를 했을 때의 값을 index로 저장하고, k % temp가 0이면 딱 맞아 떨어진 것이니, index-1을 answer에 넣어주면된다. 아닐 경우 index번째를 넣어준다.
위 경우 index = 5 // 2 = 2가 된다. k = k % 2를 하면 5 % 2 = 1이 된다. 즉 2번 지나가고 1이 남은 것이다. 그럼 3번째 것의 1번째가 답이 된다는 것을 알 수 있다. 그러므로 3을 넣어주기 위해 index가 2이므로 numberList.pop(index)를 하면 3이 들어가게된다.

이제 이걸 반복해주면 된다. n이 1 줄어들면 2가 되고, temp = 2 // 2가 되어 1이 된다. index = 1 // 1 이라 1이 된다. k = 1이 된다. 이제 answer에 index -1 즉 0번째를 넣어주면 1이 들어간다. n - 1 을 하면 n 은 1 이된다.

마지막으로 temp = 1, index = 1 // 1이므로 1이 되고 k = 1 %1이라 0이되어 첫번째 원소를 넣어주면 [3, 1, 2]가 된다.

뭔가 머리 속으로 헷갈려서 짜증났던 문제였다..

profile
3년차 프론트엔드 개발자 문건우입니다.

0개의 댓글