Python 알고리즘 인터뷰 - 문제34. 순열

leetcode 46. Permutations - https://leetcode.com/problems/permutations/description/

서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라

 

예제

입력

[1, 2, 3]

 

출력

[

[1, 2, 3],

[1, 3, 2],

[2, 1, 3],

[2, 3, 1],

[3, 1, 2],

[3, 2, 1],

]

 

풀이

순열의 조합은 다음과 같이 각 레벨에 따라 숫자 조합이 연결된 그래프 형태로 볼 수 있다.

각 레벨별 조합가능한 숫자 리스트를 elements라고 했을 때 다음과 같이 각 레벨에 따라 본인의 숫자를 제외한 나머지 elements 조합을 가지게 된다. 

순열 조합을 생성하기 위해 다음 순서로 코드를 작성한다.

prev_elements = []
def dfs(elements: list):
	...
    for e in elements:
    	prev_elements.append(e)
        
        next_elements = elements[:]
        next_elements.remove(e)
        
        dfs(next_elements)
        ...

 

해당 코드는 다음과 같이 진행된다.

elements의 리스트가 비어있으면 순열조합 하나가 완성이 된다. prev_element의 값을 results에 추가한다. 여기서 results에 prev_elements를 추가하면 참조값을 추가하게 되므로 이 후 prev_elements가 변경될 경우 정상적으로 결과가 저장되지 않는다. 따라서 prev_elements[:]를 append하여 리스트의 값을 추가할 수 있도록 한다.

prev_elements = []
results = []
def dfs(elements: list):
	if len(elements) == 0:
    	results.append(prev_elements[:])
    
    ...

 

dfs가 완료되면 다음 순열 조합을 위해 prev_elements의 마지막 조합을 pop한다.

def dfs(elements: list):
	...
    for e in elements:
		...
        
        dfs(next_elements)
        prev_elements.pop()

 

다음과 같이 prev_element = [1]이 될 때까지 반환 및 pop이 진행된다.

이 후 다음과 같이 loop를 계속 진행하며 순열 조합을 추가된다.

 

최종 코드는 다음과 같다.

def permute(nums: list[int]):
    if len(nums) == 0:
        return []

    results = []
    prev_elements = []

    def dfs(elements: list):
        if len(elements) == 0:
            results.append(prev_elements[:])

        for e in elements:
            prev_elements.append(e)

            next_elements = elements[:]
            next_elements.remove(e)

            dfs(next_elements)
            prev_elements.pop()

    dfs(nums)
    return results