[프로그래머스 파이썬] 줄 서는 방법

일단 해볼게·2023년 3월 6일
0

프로그래머스

목록 보기
51/106

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

import math

def solution(n, k):
    answer = []
    num_list = [i for i in range(1, n+1)] # 사람들
    while (n != 0):
        temp = math.factorial(n) // n # 맨 앞자리를 제외한 나머지 자리들의 경우의 수
        index = k // temp # temp가 몇 번 지나갔는지
        k = k % temp # temp만큼 지나가고 나머지

        if k == 0: # 나누어 떨어져서 index - 1을 answer에 추가
            answer.append(num_list.pop(index-1))
        else: 
             answer.append(num_list.pop(index))

        n -= 1
    
    return answer

print(solution(3, 5))

ex) n = 3, k = 5
temp = math.factorial(n) // n를 하면 6 // 3으로 2가 된다.
-> [1,2,3][1,3,2] [2,1,3][2,3,1] [3,1,2][3,2,1]로 각 숫자당 2개의 방법이 생긴다.

index = k // temp를 하면 5 // 2, k = k % temp를 하면 5 % 2 = 1이 된다.
-> 2번 지나가고 1이 남은 것이다. [1,2,3][1,3,2] [2,1,3][2,3,1] 지나가고 [3,1,2]이 남은 것
-> 3을 추가하기 위해 num_list[index]을 추가한다.

k % temp가 0이면 나누어 떨어진 것이므로 num_list[index - 1]를 추가한다.

이제 이걸 반복해주면 된다. 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]가 된다.

참고
https://velog.io/@ansrjsdn/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level3-%EC%A4%84-%EC%84%9C%EB%8A%94-%EB%B0%A9%EB%B2%95-Python

profile
시도하고 More Do하는 백엔드 개발자입니다.

0개의 댓글