[프로그래머스] 줄 서는 방법 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 가능한 모든 조합 중에서 k번째의 조합을 출력하는 문제이다.

간단하게 순열을 생각하여 permutations() 함수를 사용해 모든 조합을 구한 뒤, k번째 조합을 출력하면 효율성에서 에러 즉, 시간초과가 발생하게 된다.

하여 다른 방법으로 문제를 해결하기 위해 생각하던 중, 해당 자릿수는 각 n과 k의 값에 따라 n의 팩토리얼 값에 관련이 있다는 것을 알아냈다.

 

k를 n - 1에서부터 0까지 각 팩토리얼 값으로 나눈 몫에 해당하는 숫자를 정답 리스트에 추가해 나가면 된다.

이후 k를 팩토리얼 값으로 나눈 나머지로 새롭게 저장한다.

만약 k를 팩토리얼 값으로 나눈 나머지가 0이면 남아있는 숫자들의 조합 중 마지막 조합을 의미하므로 나눈 몫에서 -1을 해준 위치의 숫자를 정답 리스트에 추가한다.

정답 리스트에 추가해 준 값은 초기 전체 숫자 리스트에서 제거해 준다.

 

1. 팩토리얼 함수 factorial()를 사용하기 위해 math 모듈을 불러온다. import math
2. 1부터 n까지 숫자들이 있는 리스트를 생성한다. li = list(i for i in range(1, n + 1))
3. n - 1 팩토리얼부터 1 팩토리얼까지 반복하며 for i in range(n - 1, 0, -1)
   1. 만약 현재 k를 해당 팩토리얼로 나눈 나머지가 0이면 if (k % math.factorial(i) == 0)
      1. k를 팩토리얼 값으로 나눈 몫에 -1을 해준 값을 인덱스로 하는 숫자를 정답 리스트에 추가한다. answer.append(li[k // math.factorial(i) - 1])
      2. 정답 리스트에 추가해 준 숫자를 제거해 준다. del li[k // math.factorial(i) - 1]
   2. 반면에 k를 팩토리얼로 나눈 나머지가 0이 아니면 else
      1. k를 팩토리얼 값으로 나눈 몫의 값을 인덱스로 하는 숫자를 정답 리스트에 추가한다. answer.append(li[k // math.factorial(i)])
      2. 정답 리스트에 추가해 준 숫자를 제거한다. del li[k // math.factorial(i)]
   3. k의 값을 팩토리얼 값으로 나눈 나머지의 값으로 새롭게 저장한다. k %= math.factorial(i)
4.  마지막으로 남아있는 숫자를 정답 리스트에 추가해 준다. answer.append(li[0])

3. 소스코드

import math

def solution(n, k):
    answer = []
    
    li = list(i for i in range(1, n + 1))
    
    for i in range(n - 1, 0, -1):
        if (k % math.factorial(i) == 0):
            answer.append(li[k // math.factorial(i) - 1])
            del li[k // math.factorial(i) - 1]
        else:
            answer.append(li[k // math.factorial(i)])
            del li[k // math.factorial(i)]

        k %= math.factorial(i)
    
    answer.append(li[0])
    
    return answer