[파이썬 알고리즘] 12장 - 순열 (leetcode 46) ⭐

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

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]]


Input: nums = [0,1]
Output: [[0,1],[1,0]]


Input: nums = [1]
Output: [[1]]

 

---

1. DFS 이용한 풀이

# faster than 65% (40ms)
# less than 9% (14.6MB)
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(sub_list: List, remain_list: List):
            if len(nums) == len(sub_list):
                result.append(sub_list)
                return
            for i, value in enumerate(remain_list):
                dfs(sub_list+[value], remain_list[:i]+remain_list[i+1:])

        result = []
        dfs([], nums)
        return result

 

loop를 돌면 돌수록 sub_list에는 숫자가 채워지고 remain_list의 원소는 줄어드는 방식이다.

 

처음 loop에서는 dfs([1], [2, 3]), dfs([2], [1, 3]), dfs([3], [1, 2])를 호출한다.

두번째 loop에서는 dfs([1, 2], [3]), dfs([1, 3], [2]), dfs([2, 1], [3]), dfs([2, 3], [1]), dfs([3, 1], [2]), dfs([3, 2], [1])를 호출한다.

세번째 loop에서는 dfs([1, 2, 3]), dfs([1, 3, 2]), dfs([2, 1, 3]), dfs([2, 3, 1], dfs([3, 1, 2]), dfs([3, 2, 1])을 호출한다.

 

이 경우 len(nums)=3 == len(sub_list)이므로 result에 append한 뒤 함수가 종료된다.

 

---

2. itertools.permutations 이용한 풀이

class Solution2:
    def permute(self, nums):
        import itertools
        return list(itertools.permutations(nums))

위의 풀이는 코딩테스트에서는 사용할 수 있겠지만,

면접에서 코딩인터뷰를 보게될 경우 언급하는 정도로만 하고

구체적인 풀이는 위와 같은 DFS 등의 방식을 이용해서 설명하는 것이 좋다.