[프로그래머스] 줄 서는 방법(LV2 - Python)

프로그래머쓱

해당 글에서는 줄 서는 방법 문제를 Python을 이용해 풀이하고자 한다.

프로그래머스

 

🔷 문제 설명

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

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

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열했을 때, k번째 방법을 return 하는 solution 함수를 완성해 주세요.

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

 

🔷 문제 풀이

해당 문제를 보자마자 itertools의 permutations을 이용하여, 모든 조합을 뽑아내고 k번째 조합을 반환하려고 했다.

하지만 해당 방식은 시간 초과가 발생했다. k번째까지만 조합을 구하면 되지만, 입력된 n에 따라 모든 팩토리얼을 구하면서 시간초과가 발생하는 것이라고 판단했다.

 

그래서 백트래킹을 이용하여 직접 조합을 구하고 k번째 조합이 나오는 경우 함수를 종료해 주는 방식으로 구현했다.

하지만 해당 방식도 시간 초과가 발생했다.

 

🤔 어떻게 풀어야 할까?

방법이 잘 떠오르지 않아 질문하기 게시판을 참고했다.

위의 그림을 통해 규칙을 이해해 보자.

해당 그림은 n이 4일 때 나올 수 있는 순열을 일부만 나열한 것이다.

그림을 보면 첫 번째 줄에는 같은 숫자가 6개(3!)씩 차례로 반복되며, 두 번째 줄에는 2개(2!), 세 번째 줄에는 1개(1!)씩 반복되는 것을 알 수 있다. 해당 규칙을 통해 n일 경우 첫 번째 줄에는 (n-1)!개를 주기로 같은 숫자가 반복되며, 두 번째 줄에는 (n-2)!개를 주기로 같은 숫자가 반복된다는 것을 알 수 있다.

 

입력 n, k가 주어진 경우, 1부터 n까지 배열에 저장해 보자.

첫 번째로 출력되는 숫자는 어떤 것일까? 바로 배열의 k/factorial(n-1)번째에 있는 값이다.

이후 첫 번째 값으로 출력된 값을 배열에서 삭제하고, k를 factorial(n-1)로 나눈 나머지로 갱신해야 한다.

두 번째로 출력되는 숫자는 배열의 k/factorial(n-2)번째에 있는 값이 될 것이다.

이후 다시 나머지를 구하고 끝날 때까지 위 과정을 반복하면 된다.

 

🔷 코드(시간 초과)

• permutations 사용

from itertools import permutations

def solution(n, k):
    nums = [i for i in range(1,n+1)]
    perm = permutations(nums, n)

    return list(perm)[k-1]

permutations을 사용한 코드는 위와 같으며 시간 초과가 발생한다.

 

• backtracking 사용

from itertools import permutations

ans = []
cnt = 0
def backT(n, k, nums, visit):
    global cnt, ans
    
    if len(nums)==n:
        cnt += 1
        
        if cnt == k:
            ans = nums
        return
    
    for i in range(1, n+1):
        if not visit[i]:
            visit[i] = True
            backT(n, k, nums + [i], visit)
            visit[i] = False

def solution(n, k):
    visit = [False] * (n+1)
    backT(n, k, [], visit)

backtracking을 사용한 코드는 위와 같으며 시간 초과가 발생한다.

 

🔷 최종 코드

최종 코드는 다음과 같다.

 

먼저 factorial을 계산하기 위한 factorial 함수를 선언해줬다.

이후 1~n까지의 값을 차례대로 변수로 가지는 deque를 선언해줬다.

이후 n>1일 때까지 deque에 저장된 n//factorial(n-1)번째 원소를 저장 후 삭제, 나머지 계산을 반복하면서 최종 순서를 출력해주었다.

from collections import deque

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

def solution(n, k):
    ans = []
    deq = deque([i for i in range(1, n + 1)])

    while n > 1:
        fac = factorial(n-1)
        num = deq[(k-1)//fac]
        ans.append(num)
        deq.remove(num)
        n -= 1
        k %= fac

    ans.append(deq[-1])
    return ans