줄 서는 방법(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

처음에는 단순한 순열문제라 판단하여 permutions로 모든 순열을 구하고, k-1번째에 해당하는 로직으로 답안을 제출했고, 시간초과가 발생했다. 최적화를 해야했으며 dfs로 완전탐색을 하며 중간에서 답이 나오면 종료하도록 풀이를 할까 고민했지만, 그걸로는 효율성 부분에서 통과가 되지 않을 것으로 판단하여 다른 방법을 찾으려했다. 

 

모든 경우를 만들어 보는 것이 아닌, 현재 숫자보다 작은 숫자로 만들 수 있는 경우의 수를 계산을 통해 카운트 하고 넘어가는 방식을 사용하였다. 예를 들어, 아래와 같이 맨 앞자리가 4인 경우에 대해서는 앞자리가 1,2,3인 것에 대해 순회를 하지 않고, 경우의 수만 계산해서 반영하도록 하였다.

 

시간 복잡도

만약 처음 방식으로 풀었다면 n! 의 경우의 수를 탐색해야했지만, 수정한 문제 풀이의 경우 O(N) 의 시간이 걸리며, n의 최댓값이 20이기 때문에 상수시간이 걸리게 된다.

 

 

코드

from itertools import permutations

def solution(n, k):
	# 사용가능한 수 모음
    nums=[i for i in range(1,n+1)]
    
    # t개 자릿수를 만들 수 있는 모든 경우의 수 = t!
    factorial=[0]*(n+1)
    factorial[1]=1
    
    for i in range(2,n+1):
        factorial[i]=factorial[i-1]*i
        
    answer=[]
    for i in range(n-1,1,-1):
    	# 남아있는 수 중 index 번째 해당하는 숫자를 적는다
        index=(k-1)//factorial[i]
        answer.append(nums.pop(index))
        
        # 남은 자릿 수에 대해 k 번째 경우를 구한다
        k%=factorial[i]
    
    # 남아 있는 두 자리에 대해서는 아래와 같은 처리를 해준다
    # k-1 번째 수를 먼저 적어주고, 나머지 1개를 적는다
    answer.append(nums.pop(k-1))
    answer.append(nums.pop(0))
    return answer

 

 

회고

경우의 수를 통해 문제를 풀었는데 base가 0, 1 로 다르다 보니 이걸 설정해주는 부분에서 시간이 걸렸다.