[프로그래머스] Lv.2 줄 서는 방법

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

프로그래머스

 

 

1. 해결방법

이 문제를 해결하는데 거의 4시간? 정도 사용한 것 같다.
dfs와 permutations도 효율성 문제에서 아웃돼버렸다..

정답을 유추하는 데에는 10분채 안걸렸지만 효율성 테스트를 어떻게 해결할 것인가에 대해서 10분을 제외한 나머지 시간을 사용했다.
핵심 포인트는 math 라이브러리에서 factorial을 사용하는 것인데,,,,

어떻게 사용할 것인가가 가장 중요하다.

n이 3, k 가 5일 때,
[3, 1, 2]를 도출해 내야 한다.

문제에 예시에 있듯이 [1,2,3] 이라는 사람들이 있으면 줄 설 수 있는 방법은 3 x 2 x 1로 6개이다. 이는 팩토리얼로 구할 수 있다.
거기에 현재의 숫자를 나누면 각 숫자가 첫번째에 왔을 때 몇 번의 방법이 있는지 알 수 있다. 6 // 3을 하면 2가 된다. 즉, [1,2,3][1,3,2] [2,1,3][2,3,1] [3,1,2][3,2,1]로 각 숫자당 2개의 방법이 생긴다.

index는 우리가 신경써야할 기준이라 볼 수 있다. k번째를 구해야하니 k // split_number를 했을 때의 값을 index로 저장하고, k % split_number가 0이면 딱 맞아 떨어진 것이니, index-1을 answer에 넣어주면된다. 아닐 경우 index번째를 넣어준다.
위 경우 index = 5 // 2 = 2가 된다. k = k % 2를 하면 5 % 2 = 1이 된다. 즉 2번 지나가고 1이 남은 것이다. 그럼 3번째 것의 1번째가 답이 된다는 것을 알 수 있다. 그러므로 3을 넣어주기 위해 index가 2이므로 answer 리스트에 numbers.pop(index)를 하면 3이 들어가게된다.

여기서 분기문을 사용해야 하는데 k % split_number이 1일 때는 [index]를 빼주면 되지만, 0일 때는 [index - 1]로 인덱스 위치를 설정해주어야 한다.

이제 위 부분을 n이 0이 될 때까지 반복해주면 된다.


dfs도 순열 조합도 아닌 방법으로 접근한다는 것이 정말 어려웠다. 진짜 개쓰렉,,

 

 

2. 정답코드

def solution(n, k):
    import math
    answer = []
    numbers = [i for i in range(1, n + 1)]
    
    while n != 0:
        split_number = math.factorial(n) // n
        index = k // split_number
        k %= split_number
        
        if k != 0:
            answer.append(numbers.pop(index))
        elif k == 0:
            answer.append(numbers.pop(index - 1))
        
        n -= 1
    

    return answer