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

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

코딩테스트 연습 - 줄 서는 방법

문제 설명

입력으로 n과 k를 입력받는다.

1번부터 n번까지 n명의 사람들이 줄을 서 있다.

이 n명의 사람이 줄을 서는 방법에는 여러가지가 있는데, 방법을 사전 순으로 정렬하였을 때 제일 첫 방법을 1번째 방법,

마지막 방법을 n번째 방법이라 하자.

 

이 때, k번째 방법을 구하면 된다.

---

풀이 과정

처음 배열(answer)는 1부터 n번까지 차례대로 [1,2,3,...,n]으로 정렬되어 있다.

 

예시로, n = 4, k = 7이라고 하자. 즉 [1,2,3,4]배열이 이루는 모든 경우의 수에서 7번째 방법을 구하면 된다.

1번째 방법은 [1,2,3,4]

2번째 방법은 [1,2,4,3]

3번째 방법은 [1,3,2,4]... 이런식으로 나타나게 되는데,

 

각각의 자릿수에 들어가는 숫자는 규칙을 가지고 있다.

 

가장 앞자리가 1이 되는 경우는 1~6번 방법 까지이다.

왜냐하면 1을 제외한 2,3,4 세개의 숫자가 번갈아가면서 정렬을 하기 때문에 3! = 6이 되는 것이다.

 

그렇다면 앞자리가 2가 되는 경우는 7~12번 방법 까지일 것이다.

 

이렇게 앞자리를 결정하고 나면, 결정해야 할 숫자의 수는 하나씩 줄어들게 된다.

 

위의 n=4, k=7일때를 예로 들면, 처음에는 4! = 24 가지 중에 한 가지로 추려졌지만

이제는 3! = 6 가지 중에 한 가지로 추릴 수가 있는 것이다.

 

이렇게 줄여나가다 보면 내가 원하는 답을 찾게 된다.

import math


def solution(n, k):
    answer = [i for i in range(1, n + 1)]
    stack = []
    k = k-1


    while answer:
        # k / (n-1)! 을 했을 때의 몫이 맨 첫번째 자리
        a = k // math.factorial(n - 1)
        stack.append(answer[a])
        del answer[a]

        # k를 줄여야함.
        k = k % math.factorial(n - 1)
        n -= 1


    return stack

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !