[LeetCode]Permutations

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

Permutations - LeetCode

 

문제 분석

주어진 숫자로 만들 수 있는 모든 순열을 구하는 문제입니다.

 

처음 시도한 답안

import itertools


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

        permutations = [list(x) for x in permutations]

        return permutations

접근 방법

1. 파이썬에서 제공해주는 itertools 모듈의 permutations 메소드를 이용합니다.
2. 정답 포맷에 맞게 변환합니다.

파이썬에서 순열을 구할 수 있는 메소드가 존재해서 풀이 자체는 쉽게할 수 있었습니다. 다만, 다른 풀이 방법은 어떤것이 있을지 찾아보았습니다.

 

두번째로 시도한 답안 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        """
        Level0: []
        level1: [1]                  [2]              [3]
        level2: [1,2]    [1,3]       [2,1] [2,3]      [3,1] [3,2]
        level3: [1,2,3]  [1,3,2]     [2,1,3][2,3,1]   [3,1,2][3,2,1]          
        """

        answer = []

        def dfs(i, visited):
            if len(visited) == len(nums):
                answer.append(visited[:])
                return

            for i in range(len(nums)):
                if nums[i] not in visited:
                    visited.append(nums[i])
                    dfs(i, visited)
                    visited.pop()
    
        dfs(0, [])

        return answer

접근 방법

1. dfs를 통해 재귀적으로 순열을 생성해나갑니다.
2. 선택한 숫자가 nums의 숫자와 동일하다면 정답에 추가합니다.
3. 모든 경우의 수를 탐색할 수 있도록 반복을 통해 dfs를 호출합니다.
   1. 단, 이미 방문한 숫자의 경우는 호출하지 않습니다. (중복된 숫자 사용 불가능 처리)
   2. 또한, 방문에 추가한 원소를 dfs 호출 후에 pop하여 같은 레벨에서 다음 숫자를 탐색할 수 있도록 합니다. 

주석에 담긴 레벨을 참고하면 어떤 방식으로 탐색이 진행되는지 알 수 있습니다. 부연 설명을 하면 다음과 같습니다.

Level 2 에서 [1, 2]를 추가하고 pop하여 [1, 3]에 대해서도 탐색을 가능하도록 만드는 것입니다.

이 과정이 없다면 주석 기준 오른쪽으로 탐색하는 과정을 수행할 수 없습니다.