[프로그래머스][level3] 줄 서는 방법 -python

문제 링크

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

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

풀이 - 다른 블로그 참고 

• 처음엔 순열로 풀었는데 시간초과 

# 시간 초과 
from itertools import permutations 
def solution(n, k):
  permute = list(permutations(range(1,n+1),n))
  
  return permute[k-1]

• 팩토리얼 이용 

앞자리에 각 숫자가 오는 경우의 수는 뒷 숫자들 배열의 경우의 수와 같으므로 (n-1)!이다.

예를 들어,  n=4, k=7이라고 하면 제일 앞에 1이 오는 경우의 수는 2, 3, 4 가 배열되는 경우의 수인 3!이다. 

따라서 앞자리가 1이 되는 경우는 1-6번까지, 2가 되는 경우는 7-12번까지가 된다. 

따라서 k / (n-1)! 했을 때 몫이 맨 첫번째 자리가 되는 것이다.  

맨 앞자리가 정해졌으면 다음 결정해야될 수들은 하나씩 줄어들고, k도 k / (n-1)!의 나머지로 줄어든다. 

이를 모든 숫자가 배열될 때까지 반복한다. 

import math

def solution(n, k):
  answer = []
  
  # 각 숫자들 
  num = [i for i in range(1,n+1)]
  # 배열은 0부터 시작하므로 -1 
  k = k - 1 

 # 숫자가 다 배열될때까지 반복 
  while n > 0 :
    # 맨 앞자리에 올 숫자의 인덱스 
    a = k // math.factorial(n-1)
    # 구한 인덱스에 해당하는 숫자 answer에 넣음 
    answer.append(num[a]) 
    # 배열된 숫자 제거 
    del num[a]
    
    # k 줄이기 
    k = k % math.factorial(n-1)
    n -= 1 

  return answer

+ 2022.04.28 다시 풀이 

- 백트래킹으로 풀었는데 시간 초과 : 실제 경우의 수를 다 구해서 k번째 값을 가져오는 건 시간초과가 발생하는 듯 하다. 

answer = []
# 백트래킹으로 줄세우기 
def dfs(s,n):
    global visited 
    
    if len(s) == n:
        answer.append(list(map(int, s)))
    for i in range(1,n+1):
        if not visited[i]:
            visited[i] = True 
            s.append(i)
            dfs(s,n)
            visited[i] = False
            s.pop()
        
def solution(n, k):
    global visited

    s = []
    visited = [False] * (n+1)
    dfs(s,n)
        
    return answer[k-1]