줄 서는 방법

프로그래머스

 

백트래킹으로 푸는 문제.

---

 

 

첫번째 풀이 - 시간 초과

from itertools import permutations

def solution(n, k):
    answer = []
    
    candidate_list = list(permutations(range(1, n+1)))
    
    return candidate_list[k - 1]

 

이 문제에서 n의 범위가 20 이하인 자연수이므로 만약 permutations를 통해 구하면 최대 20!만큼의 후보들을 리스트에 저장해야 한다.

그러므로 위 풀이는 불가능하다. 20!개의 원소를 모두 리스트에 저장시킬 수 없기 때문이다.

그래도 혹시 몰라서 제출해봤는데, 역시 효율성 테스트에서 모두 시간초과가 떴다.

 

---

두번째 풀이 - 정답

import sys
sys.setrecursionlimit(10**5) # 재귀 범위 설정

# num!를 반환하는 함수
def factorial(num):
    if num == 1 or num == 0:
        return 1
    return num * factorial(num - 1)


# 백트래킹
def backTracking(arr, k, result):    
    if len(arr) == 0: # 모든 arr 리스트를 탐색한 경우 result를 반환       
        return result
    
    n = len(arr)
    temp_factorial = factorial(n - 1)
    
    for i in range(n):
        k -= temp_factorial
        if k <= 0: # 만약 k가 0 이하가 되는 경우
            temp = arr[i] # index에 해당하는 arr값을 arr에서 제거하고 result에 추가
            arr.remove(temp)
            result.append(temp)
            return backTracking(arr, k + temp_factorial, result) # 백트래킹

def solution(n, k):
    answer = backTracking(list(range(1, n+1)), k, [])

    return answer

 

백트래킹으로 문제를 쉽게 해결할 수 있다.

 

만약 n이 4이고 k가 17인 경우를 생각해보자.

 

4명의 사람이 줄을 서는 방법은 크게 4가지로 나눌 수 있다.

 

1 - ....

2 - ....

3 - ....

4 - ....

 

그리고 각 방법은 3!만큼의 경우의 수를 가지고 있다.

 

그러므로 n명의 사람이 줄을 서는 방법은 (n-1)명의 사람이 줄을 서는 경우의 수 * n이다.

그러므로 앞 번호에서 부터  k - (n-1)!을 해주면서  k가 0 이하가 되는 경우 그 때의 번호를 result 리스트에 앞에서부터 추가해주면 된다.

 

그리고 백트래킹을 돌아야하므로 기존 arr에서 해당 번호를 제거하고, result 리스트에 해당 번호를 추가해준다. 그리고 k를 갱신해준다.

백트래킹을 돌면서 arr의 길이가 0이 되는 경우, 즉 모든 번호를 탐색한 경우 result 리스트를 반환하면 된다.

 

---

참고

 

코드는 금방 작성했는데 

# 백트래킹
def backTracking(arr, k, result):    
    ....
            return backTracking(arr, k + temp_factorial, result) # 백트래킹

 

위 코드에서 이 부분을 

 

# 백트래킹
def backTracking(arr, k, result):    
    ....
            backTracking(arr, k + temp_factorial, result) # 백트래킹

 

return을 빼주는 방식으로 코드를 작성했다가 list index out of range 오류가 떠서 이 부분 오류를 찾느라 시간이 오래 걸렸다.

 

백트래킹 문제를 오랜만에 풀어서 기초적인 실수를 했다.

그래도 실수를 통해서 다시 감을 잡아서 다행이다.