[programmers] Lv2 줄 서는 방법 - Python

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

프로그래머스

 

 

 

<문제 풀이>

- 문제를 처음 봤을 때 모든 경우를 구해서 순서에 맞는 것을 찾는 방식인 combination을 이용했을 경우 시간 문제가 발생할 것 같았다.

<수정 전>

- 그래서 처음 한 생각은 다음과 같다.

-  1 ~ n까지의 숫자로 만들수 있는 조합에서 첫 번째 오는 수 하나를 고정하고 만들 수 있는 경우의 수가 factorial(n-1), 두 번째는 factorial(n-2) ... 이런식으로 개수를 알 수 있다는 점이다. 이렇게 구한 수들을 통해 더해가면서 k번째를 찾아가는 것이다.

- k번째 있는 순서 배열을 구할 방법이다. 순서는 오름차순이기 때문에 1부터 n까지의 숫자 리스트를 준비한다.

- 이후 k값에서 factorial(n-1)을 하면 몫과 나머지가 나오는데, 몫은 숫자 리스트에서 몫에 해당하는 순서에 있는 숫자가 answer가 되는 곳에서 첫 번째로 오는 숫자이다.

- 중복을 제거하고자 숫자 리스트에서 해당 숫자를 제거한 후, 좀 전에서 생긴 나머지가 k의 역할을 할 것이고 factorial(n-2)로 다음 순서로 올 숫자를 구한다.

- 이러한 과정들을 반복해서 정답을 도출했다. 

- 하지만 내가 작성한 수정전 코드에서는 단순하게 생각나는 대로 작성했고, 그 결과 중간에 나머지가 0이 되고 아직 숫자가 남은 경우 answer 리스트에 남은 숫자들을 정렬하지 못했다. 중간에 나머지가 0이 되는 경우는 앞에 정렬한 숫자를 제외하고 나머지 뒷 부분에 해당하는 부분이 가장 커야하기 때문에 남은 숫자를 역순으로 넣어주는 작업을 해주어야했다.

 

<수정 후>

- 위와 같은 코드를 조금더 간결하게 하기 위해 고민하던 중 다른 사람풀이를 참고했다.

- 해당 방식은  1 ~ n까지의 숫자 리스트에서 인덱스로 접근하여 나의 코드에서 불필요한 부분들을 모두 제거해주는 깔끔한 코드여서 따로 작성해보았다.

 

 

 

<Code>

수정 전

from math import factorial


def solution(n, k):
    answer = []
    numbers = list(range(1, n + 1))
    cnt = n - 1
    x = factorial(cnt)

    while True:
        a, b = divmod(k, x)
        if b == 0:
            answer.append(numbers[a - 1])
            numbers.pop(a - 1)
            break
        else:
            answer.append(numbers[a])
        numbers.pop(a)
        k = b
        x //= cnt
        cnt -= 1

    if len(numbers) != 0:
        for i in range(len(numbers) - 1, -1, -1):
            answer.append(numbers[i])

    return answer

 

수정 후

from math import factorial


def solution(n, k):
    answer = []
    numbers = list(range(1, n + 1))

    while n != 0:
        x = factorial(n - 1)
        answer.append(numbers.pop((k - 1) // x))
        n, k = n - 1, k % x

    return answer

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.