leetCode 46. Permutations

https://leetcode.com/problems/permutations/description/

Permutations - LeetCode

 

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

주어진 숫자의 조합을 생성하는 문제이다.

 

숫자별로 탐색하며 만들거나, 아니면 itertools 라이브러리를 사용한다.

 

[로직]

# 주어진 리스트 숫자별로 시작하는 순열을 탐색한다.

# 이미 탐색한 숫자를 제외하고 다음 탐색할 리스트를 만든다. (next_elements)

# 탐색한 숫자는 다른 리스트에 저장한다. (prev_elements)

# 다음 탐색할 next_elements를 가지고 dfs를 시작한다.

# 처음 주어진 elements 를 다 탐색해서 받은 다음에 탐색할 리스트 개수가 0이 되면,

prev_elements에는 elements의 전체 숫자가 탐색한 순서대로 들어 있다. 

results 리스트에 prev_elements를 복사해서 추가한다. (리스트 내 리스트로)

# 끝까지 다 돌고 나왔으면 하나 위 단계(트리로 치면 부모 노드)에서 선택하지 않은 숫자(트리로 치면 노드)로 가서 탐색한다. prev_elements에서 제일 끝 숫자를 pop 한다. (이미 방문한 자식노드 기록을 없앤 채로 같은 레벨의 다른 자식노드부터 시작)

# 제일 부모 리스트를 끝까지 다 돌았으면 전체 탐색 끝. 

# 전체 탐색한 결과 반환

 

[ 방문 과정 ]

#1

elements = [1, 2, 3]

e = 1

next_elements = [2, 3]

prev_elements = [1]  ---> prev_elements는 dfs 밖에 선언되어 모든 dfs 재귀로 도는 애들이 같은 리스트를 바라본다.

dfs 1-2 호출

 

#1-2

elements = [2, 3]

e = 2

next_elements = [3]

prev_elements = [1, 2]

dfs 1-3 호출

 

#1-3

elements = [3]

e = 3

next_elements = []

prev_elements = [1, 2 ,3]

dfs 1-4 호출

 

#1-4

elements = []

results.append([1,2,3])

 

--> 더 수행할 게 없으므로 dfs 1-3으로 돌아감

 

#1-3 

여기서 주어진 리스트 elements에서 3 말고 다른 선택지가 있는지 확인

이미 방문한 노드 prev_elements에서 가장 마지막에 방문한 3을 뺌

prev_elements = [1,2]를 가지고, dfs 1-3에서 3 말고 방문할 수 있는 노드 확인

없음

 

-> dfs 1-2로 돌아감

 

#1-2

주어진 리스트 elements에서 2를 방문하지 않았을 때의 경우로 탐색 들어가야 함

prev_elements에서 2를 뺌

elements = [2, 3] 을 가지고, 다음 탐색 숫자가 2가 아닌 경우 (다음 for문) 탐색

elements = [2, 3]

e = 3

next_elements = [2]

prev_elements = [1, 3]

dfs 1-3 호출

..

 

 

dfs를 끝까지 가고 재귀 반환되어 부모 노드로 돌아간 다음에는, 이미 방문한 자식노드 말고

다음 자식노드부터 시작했을때의 경우를 탐색해야 함.

이미 방문한 리스트에서, 기존 방문했던 자식노드를 뺀 다음, 새로 방문하는 자식노드를 추가해서 탐색을 시작함.

 

반복하다가 제일 부모 노드에서 전체 자식을 다 탐색하고 나면

모든 자식노드를 끝까지 탐색했을때의 순서를 가진 results가 생김.

 

result를 반환하면, 전체 가능한 순열 리스트임

 

#leetcode 46.Permutations
from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        prev_elements = []

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

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

                prev_elements.append(e)
                dfs(next_elements)
                prev_elements.pop()

        dfs(nums)
        return results

    #        return list(map(list, itertools.permutations(nums)))

solution = Solution()
print(solution.permute([1,2,3]))

 

아니면 itertools 모듈을 사용해서 간단하게 구현할 수 있다.

C라이브러리로 구현되었으므로 속도도 빠르고 이미 잘 구현되어 만들어서 쓰는 것보단 문제생길 일도 없다.

 

itertools.permutations(리스트)

로 하면 (1,2,3), (1,3,2) , .. 로 튜플 모음이 생성된다.

리스트 반환하라고 문제에 정의 되어 있으므로 map을 사용하여 list로 변환해준뒤

다시 리스트로 감싸서 반환한다.

return list(map(list, itertools.permutations(nums)))

 

 

 

# 파이썬 알고리즘 인터뷰 책 참고