[LeetCode/Python] 46. 순열(Permutations)

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

 

Example:

 

Input: nums = [1,2,3]

 

Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

 

 

 

 

 

 

 

1. 내가 직접 푼 코드

 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(stack=None):
            if stack is None:
                stack = []
            if len(stack) == len(nums):
                output.append(stack)
                return
            for w in nums:
                if w not in stack:
                    dfs(stack+[w])
 
 
        output = []
        dfs()
        return output

 

해설:

 

dfs를 재귀로 구현하였다.

 

stack에 하나씩 추가해가며 최종적으로 길이가 다 찼을 때 output에 입력하고 리턴하였다.

 

재귀 함수를 쓸 때는 입력값을 어떻게 주느냐를 고민하는데 시간이 많이 드는 것 같다.

 

 

 

 

 

 

 

** 깔끔한 코드 **

 

 

 

 

2. 모든 조합 탐색

 

 

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

 

해설:

 

나와 같이 dfs를 재귀로 구현한 코드이다.

 

prev_elements에 nums가 들락날락거리게 되는데

 

elements의 길이가 0일 때

 

즉, prev_elements가 result에 들어갈 요건이 됐을 때

 

result에 추가하게 되는데 왜 prev_elements [:]라 했을까?

 

그 이유는 prev_elements라 하면 results에 참조된 prev_elements가 들어가는 거라

 

prev_elements가 바뀔 때 마다 results에 들어있는 값도 계속 바뀐다.

 

그래서 prev_elements.copy() 혹은 prev_elements.deepcopy() 같은 걸 붙여줘야 한다.

 

 

 

 

 

3. itertools를 모듈 사용

 

 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))

 

해설:

 

itertools라는 모듈이 있다.

 

여기에 리스트를 넣으면 모든 순열이 나온다.

 

코딩 테스트에선 써도 되지만

 

코딩 인터뷰 때는 "이걸 써도 되지만"이라 언급하며 위와 같은 식으로 풀자.

 

저렇게 풀면 튜플 값이 리턴되는데 답은 맞지만 리스트를 리턴 하고 싶다면

 

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

 

을 쓰자.