[프로그래머스 level3 줄 서는 방법] 규칙 찾기

해결해야하는 문제는 다음과 같았다.

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

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

 

아주 오랜만에 코딩해볼겸 풀어보았다!

 

첫번째 아이디어는 다음과 같다.

1. itertools를 이용하여 모든 순열 경우의 수 구하기

2. 파이썬 내장함수 sort를 통해 sorting하기

3. k-1번째에 해당하는 리스트 return하기

 

아이디어를 바탕으로 작성한 코드는 다음과 같다.

(정확성 테스트 중 두 개의 테스트케이스에서 시간 초과가 나고, 효율성테스트는 하나도 통과가 안된다.)

from itertools import permutations

def solution(n, k):
    # itertools 순열 경우의 수 구하기
    arr = [i for i in range(1,n+1)]
    answer = list(permutations(arr,n))
    # sort
    answer.sort()
    # k-1번째 원소 return
    return list(answer[k-1])

 

 

효율성 테스트를 위해 고민한 아이디어는 다음과 같다.

하나씩 쓰며 규칙을 찾은 뒤, 어떤 방식으로 작성할지 고민하였다.

 

1. 0!부터 n!까지의 factorial을 저장, 1~n의 숫자를 num 배열에 저장

2-1. n>2인 경우, 해당 자리에 와야하는 숫자 구함

  2-1-1. _ _ _ : 3번째 자리수의 경우 (3-1)! 개의 숫자를 가질 수 있음

    - k 가 (n-1)!로 나누어 떨어지지 않는 경우

        - num에서 k//(n-1)! 번째 숫자를 가져옴

        - 추후, k에서 현재 자릿수에서 계산된 값을 빼기 위해 tmp에 idx*fact[n-1] 저장

 

    - k가 (n-1)!로 나누어 떨어지는 경우

       - num에서 k//(n-1)! - 1 번째 숫자를 가져옴

       - 추후, k에서 현재 자릿수에서 계산된 값을 빼기 위해 tmp에 idx*fact[n-1] 저장

 

3. 이번 자릿수에서 빠지는 수를 answer에 저장

4. k와 n을 업데이트

  - k = k-tmp

  - n = n-1

 

5. answer에 마지막으로 남은 num 저장

 

 

 

아이디어를 바탕으로 작성한 코드는 다음과 같다.

def solution(n, k):
    answer = []
    num = [i for i in range(1,n+1)]
    tmp = 1
    fact = [1]
    for i in range(1,n+1):
        tmp *= i
        fact.append(tmp)

    while n > 1 :
        if n==2 and k==2:
            idx = 1
        elif n==2 and k==1:
            idx = 0
        elif k%fact[n-1]>0 :
            idx = k//fact[n-1]
            tmp = idx*fact[n-1]
        else :
            idx = k//fact[n-1]-1
            tmp = idx*fact[n-1]
        answer.append(num[idx])
        num.pop(idx)
        k -= tmp
        n -= 1

    answer.append(num.pop())

    return answer

print(solution(4,10))