[프로그래머스] 줄 서는 방법 (python)

문제

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

 

n명의 사람들을 나열하는 방법을 사전 순으로 나열했을 때, k번째 방법을 반환하는 문제이다. 

 

 

풀이 

 

tmp

아직 사용하지 않은 숫자를 오름차순으로 tmp 배열에 담았다. 

 

 

tmp의 인덱스 구하기

k번째 배열에서 i번째에 올 숫자를 구한다고 했을 때(1 ≤ i ≤ n), k를 남아있는 자릿수의 팩토리얼, 즉 (n-i)!으로 나누어 주었을 때의 몫이 사용하지 않은 숫자를 담은 tmp에서의 인덱스를 나타낸다. 

 

[[1 2 3], [1 3 2], [2 1 3], [2 3 1], [3 1 2], [3 2 1]]

여기서 k가 1과 2일 때 첫번재 자리수를 구해보면 다음과 같은 결과가 나온다. 

1일 때는 1/(3-1)!=0

2일 때는 2/(3-1)!=1

 

두 값이 모두 숫자 1을 가리키는 0의 인덱스값을 가져야 하므로 올림을 해준 뒤 1을 빼주었다. 

 

 

팩토리얼 

팩토리얼 계산을 위해 처음에는 함수를 따로 두었는데 효율성 테케가 통과되지 않아서 한번만 팩토리얼 연산을 수행하고 그 뒤로는 n-i 로 나눠주었다. 또한 한번의 팩토리얼 연산을 reduce함수를 통해 코드를 간소화했다. 

def factorial(num):
    result = 1
    while num > 0:
        result *= num
        num -= 1

    return result
    
    
 case = reduce(lambda x,y:x*y,range(1,n))

 

 

k, case 갱신

i번째 자리의 숫자를 찾은후,

k는 팩토리얼 값인 case로 나눈 나머지로 설정했고, case는 n-i로 나누어 주었다. 

 

 

예외 처리 

k가 0일 때는 가능한 경우의 수에서 마지막 배열이므로 남은 숫자 배열을 거꾸로 정렬해 answer에 붙여주었고,

k가 1일 때는 가능한 경우의 수에서 시작 배열이므로 남은 숫자 배열을 answer에 붙여주었다. 

 

 

코드 

from functools import reduce
import math

def solution(n, k):
    answer = []
    tmp = [i + 1 for i in range(n)]

    i = 1
    case = reduce(lambda x,y:x*y,range(1,n))
    while i < n:
        if k==0:
            tmp.sort(reverse=True)
            answer+=tmp
            break
        if k==1:
            answer+=tmp
            break
        
        idx = math.ceil(k/case)-1   
        answer.append(tmp[idx])
        tmp.pop(idx)
        
        
        k %= case
        case //= n-i
        i += 1
        
    return answer

 

 

회고

처음 풀었을 때 인덱스를 구하는 부분에서 나누어 떨어졌을 때를 고려해주지 않아서 오류를 찾는데에 오래걸렸다. 

무작정 규칙을 찾았다고 바로 코드로 넘어가지 않고 모든 경우를 고려한 뒤 코드를 작성해야겠다. 

 

 

다른 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/12936/solution_groups?language=python3

 

프로그래머스의 다른 풀이를 보고 factorial 내장 함수가 있다는 것을 알게되었다 .. 너무 복잡하게 풀었다 나

def setAlign(n, k):
    from math import factorial
    answer = []
    order = list(range(1,n+1))
    while n!=0 :
        fact = factorial(n-1)
        #answer.append(order.pop(k//fact-1 if k%fact ==0 else k//fact))
        answer.append(order.pop((k-1)//fact))
        n,k = n-1, k%fact
    return answer