[Seop's의 코드풀이] 프로그래머스 줄 서는 방법 - Python

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

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

 

 

문제 요약

서로다른 자연수 n 개를 나열하는 방법의 수 중 k 번째 수는 무엇인지 확인하는 문제이다.  

모든 경우를 나열한 후 사전순으로 정렬 할 수 있지만 시간이 너무 오래 걸리는 문제가 발생한다.  

그러므로 우리는 바로 K 번째 수를 구할 수 있어야 한다.  

 

문제풀이 아이디어

• 서로다른 n개의 자연수로 이루어진 수열의 맨 앞자리가 수가 같은 경우는 한정되어 있다.
• 맨 앞자리수 부터 차례대로 구해 나간다면 모든 수열을 구하지 않고도 K번재 수를 구할 수 있다. 
  구하는 방법은 다음과 같이 구할 수 있다.  
  
  1. 1 ... n 까지의 자연수가 존재하는 배열을 생성한다. 
  2. 맨 앞자리가 같은 수의 수열의 개수는 (1번 배열의 길이 - 1)! 개 이다.(! : 팩토리얼)
  3. k 를 2번에서 구한 값으로 나눈 값에 해당하는 인덱스를 추출하여 정답 배열에 추가한다. (1번배열에서 삭제 후 정답배열에 추가)
     나머지 값이 0 이라면 나눈 값에서 -1 을 진행한다. 
  4. 1번 배열이 없어질때까지 2~3번 과정을 반복한다.

코드

전체 코드는 다음과 같습니다. 피드백과 질문은 언제나 감사드립니다. 

import math
def solution(n, k):
    answer = []
    num = [i for i in range(1, n+1)]
    while num :
        mid = math.factorial(len(num) - 1)
        v, r = divmod(k,mid)
        if r == 0 : v -= 1
        answer.append(num.pop(int(v)))
        k = k - v*mid 


    return answer