본문 바로가기

⏳ 알고리즘/python 알고리즘 문제 풀이

알고리즘 - LV3.줄 서는 방법

문제

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

 

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

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람

programmers.co.kr

 

코드

1) itertools모듈의 permutations이용 => 경우의 수를 불필요하게 많이 계산하게 됨

import itertools

def solution(n, k):
    return list(itertools.permutations(range(1,n+1), n))[k-1]

 

2) math모듈의 factorial이용

import math

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

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

    return answer