[프로그래머스 programmers] 줄 서는 방법 / 레벨 3

https://programmers.co.kr/learn/courses/30/lessons/12936?language=python3 

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

def solution(n, k):
    def factorial(a):
        if a==0:
            return 1
        val = a
        while a>1:
            a -= 1
            val *= a
        return val
    
    used = [0]*n
    
    global count
    count = 0 
    answer = [0]*n
    
    def dfs(c, ftr):
        global count
        print(c, ftr)
        if c == n :
            count += 1  
        if count == k:  # find
            return True
        
        ftr /= (n+1-c)
    
        if count + ftr < k:
            count += ftr
            return
        
        for num in range(1, n+1):
            if used[num-1]== 0:
                used[num-1] = c+1
                if dfs(c+1, ftr):
                    return True
                used[num-1] = 0
                
    dfs(0, factorial(n+1))
    
    for i in range(n):
        ord = used[i]
        answer[ord-1] = i+1
    return answer

나름 큰 깨달음을 얻었는데 

재귀를 중간에 종료하는법

 

백준은 그냥 quit()으로 답을 출력하면서 프로그램 자체를 종료하면 되었지만

프로그래머스에선는 답을 solution함수의 리턴 값으로 넘겨줘야 하므로 맘대로 quit() 해버리면 안된다.

이럴 때 재귀를 어떻게 중간에 끊을 수 있을 지 고민을 해봤는데

 

가장 간단한 방법은 재귀 종료 시점에 return 값을 true로 넘겨주고

아래 부분에 재귀 함수가 사용된 부분에서 조건문을 만들어서 if true -> return true 이런 식으로 만들어주는 것이다. 그 예시가 위의 코드다. 

 

import math
def solution(n, k):
    used = [0]*n
    global count
    count = 0 
    answer = [0]*n
    
    def dfs(c, ftr):
        global count
        if c == n :
            count += 1  
        if count == k:  # find
            return True
        
        ftr /= (n+1-c)
        if count + ftr < k:
            count += ftr
            return
        
        for num in range(1, n+1):
            if used[num-1]== 0:
                used[num-1] = c+1
                answer[c] = num
                if dfs(c+1, ftr):
                    return True
                used[num-1] = 0
                
    dfs(0, math.factorial(n+1))
    return answer

개선사항

- import math로 factorial 사용

- 재귀할 때 answer 바로 만들기