[LeetCode] 46. Permutations (그래프)

문제

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

Permutations - LeetCode

 

주어진 배열의 순열을 구하자.

 

풀이 1 - 백트래킹

 

순열을 만들기 위해 check 배열을 사용하여 순서를 지정해주었다.

시간 : 39ms

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans, tmp = [], []
        check = [False]*len(nums)
        
        def dfs(cnt):
            if cnt == len(nums):
                ans.append(tmp[:])
                return
            for i in range(len(nums)):
                if not check[i]:
                    check[i] = True
                    tmp.append(nums[i])
                    dfs(cnt+1)
                    check[i] = False
                    tmp.pop()
        
        dfs(0)
        return ans

 

풀이 2 - permutations

 

파이썬 내장 함수로 찹찹. 코드 길이 무엇...

시간 : 48ms

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

 

책 풀이 - 백트래킹

 

next_elements에서 원소 e를 제거하고, prev_elements에서 원소 e를 추가한다.

dfs에 next_elements를 파라미터로 넘긴다.

백트래킹이기 때문에 dfs가 끝나면 prev_elements에서 pop()을 한다.

시간 : 65ms

 

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

 

What I learned

객체 복사

파이썬의 특징은 모든 것이 '객체'라는 것이다.

그래서 별도로 값을 복사하지 않는 한, 변수에 값을 할당하는 모든 행위는 값 객체에 대한 참조가 된다.

 

참조가 되지 않도록 값 자체를 복사하려면 어떻게 해야 할까? 

 

가장 간단한 방법은 [:]로 처리하는 것이다.

a = [1 2, 3]
b = a
c = a[:]

좀 더 직관적으로 처리려면 copy()를 사용할 수도 있다.

d = a.copy()

단순한 리스트는 [:] 또는 copy()로도 충분하지만, 복잡한 리스트의 경우 copy.deepcopy()로 처리해야 한다.

import copy
a = [1, 2, [3, 5], 4]
b = copy.deepcopy(a)

 

총평

내가 푼 풀이(소싯적 알고리즘 공부할 때 습득함)의 시간이 더 빠르다. 아마도 C style이라서 그런 것 같다. (책 풀이는 python style)