ch12-3(leetcode 46). 순열

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 46번 ( https://leetcode.com/problems/permutations/ )

 

풀이 1. (교재 참고)

DFS를 재귀 함수로 사용해서 풀 수 있다. 

이때 지금까지 탐색한 경로(노드)를 저장하는 prev_elements와 최종 탐색한 결과만을 저장하는 results 두 개의 변수를 사용한다. 

 

dfs() 라는 이 내부 함수는 숫자 리스트를 매개변수로 받는다. 그리고 다음에 탐색할 숫자 리스트를 저장하는 next_elements 변수에다가 매개변수로 받은 리스트 값을 할당한다. 

이때 = 를 사용해서 변수를 그대로 할당하면 파이썬에서는 값을 복사하는 것이 아니라 참조하게 되므로, [:]을 통해 할당해 준다. 

next_elements = elements		# assign by reference
next_elements = elements[:]		# assign by value

 

for loop를 돌면서 임의로 원소를 하나 빼낸 뒤 next_elements 리스트에서는 해당 원소를 제거한다. 왜냐하면 현재 탐색한 노드(경로)이므로 다음 dfs() 시행에서는 탐색하지 않을 것이기 때문이다. 

 

반대로 prev_elements 리스트에다가는 해당 원소를 추가한다. 현재 탐색한 노드를 기록해야 하기 때문이다. 

그 다음에 next_elements를 매개변수로 두고 dfs()를 다시 호출한다. 

dfs(next_elements)

 

dfs()의 재귀적 시행은 다음에 탐색할 노드가 없어지면 종료된다. 종료될 때는 그동안 탐색한 노드 경로를 결과를 저장하는 변수인 results에 할당해 준다. 

마찬가지로 results에 값을 추가할 때는 prev_elements의 값을 참조하지 않고, 복사해서 저장해야 하므로 [:]으로 문자열을 슬라이싱 및 복사해서 사용한다. prev_elements는 재귀적으로 dfs()가 시행되면서 계속 변경되는 값이기 때문이다. 

if len(elements) == 0:
	result.append(prev_elements[:])

 

이 모든 과정은 dfs()가 한 번 호출되면 이후에는 재귀적으로 시행되므로 처음에 dfs()를 한 번만 호출해 주면 된다. 

 

다음 예시를 보자. 

nums = [1, 2, 3, 4] 라는 입력이 주어질 때, 출력으로 [1, 2, 3, 4]가 추가되는 경우를 자세히 살펴보자. 

 

step 1. dfs([1, 2, 3, 4])

elements = [1, 2, 3, 4]

prev_elements = [1]

next_elements = [2, 3, 4]

 

step 2. dfs([2, 3, 4])

elements = [2, 3, 4]

prev_elements = [1, 2]

next_elements = [3, 4]

 

step 3. dfs([3, 4])

elements = [3, 4]

prev_elements = [1, 2, 3]

next_elements = [4]

 

step 4. dfs([4])

elements = [4]

prev_elements = [1, 2, 3, 4]

next_elements = []

 

step 5. dfs([])

elements = []

len(elements) == 0 이므로 더 이상 dfs()가 호출되지 않고 results 변수에 prev_elements([1, 2, 3, 4])가 추가된다. 

 

 

풀이 2. (교재 참고)

파이썬에서 기본으로 제공하는 itertools 모듈을 이용해도 풀 수 있다. 

 

itertools에서는 여러 메소드를 제공하는데 그 중 하나가 리스트를 매개변수로 받아서 리스트의 원소에 대해 가능한 순열 리스트를 리턴하는 permutations() 메소드이다. 

itertools.permutations(list_name)

 

permutations() 외에도 가능한 조합 리스트를 리턴하는 combinations(), 중복 조합 리스트를 리턴하는 combinations_with_replacement(), 가능한 cartesian product 경우를 리스트로 리턴하는 product() 등 다양한 메소드가 있다. 

 

이 모듈을 사용하면 코드를 한 줄로 쓸 수 있다. 

return list(itertools.permutations(nums))

 

참고한 포스트

https://docs.python.org/3/library/itertools.html#module-itertools