프로그래머스 (Lv2) 줄 서는 방법

프로그래머스 Lv.2 “줄 서는 방법”

n명의 사람이 줄서는 방법 중 k번째로 줄을 서는 방법을 출력하는 함수를 구현하는 문제

n은 20 이하의 자연수이며, k는 n! 이하의 자연수이다.

나의 풀이

처음에는 줄을 서는 방법을 모두 나열해야 할 것이라 생각하여 순열 (itertools.permutations) 함수를 이용하였으나, 효율성 문제를 통과하지 못하였다.

순열 대신 factorial 함수와 divmod 함수를 이용하면 효율성 문제 또한 통과할 수 있다.

• factorial 함수를 직접 정의하는 것보다 math 라이브러리에서 import 하는 것이 더 효율적이다.

• factorial 함수의 정의 예시

def fac(n):
    if n>1:
        return n*fac(n-1)
    if n==1 or n==0:
        return 1

문제풀이 코드

from math import factorial

def solution(n, k):
    answer = []
    numbers = [i for i in range(1, n+1)]
    k -= 1     # k가 1부터 시작하므로 -1 (0부터 시작) 처리
    
    for i in range(n, 0, -1):
        div, k = divmod(k, factorial(i-1))
        answer.append(numbers.pop(div))
        
    return answer 
    

TMI) 프로그래머스 점수 18점 상승을 안겨준 기념비적인 문제이다 :)

오류나 틀린 부분이 있을 경우 언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다!

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기