❗️[LEET CODE] 46. Permutations ( 객체 복사 )

# Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Constraints: 1 <= nums.length <= 6 -10 <= nums[i] <= 10 All the integers of nums are unique.

 

# My Answer

1.

def dfs(nums):

     for n in nums:

         if len(nums)==2: 순서 바꾼거, 순서 그대로인 리스트 두개 리턴

         else: 

                결과 리스트에 n + dfs(nums에서 n 뺀 리스트) 삽입

---> Time Out

 

2. 리스트에 하나씩 추가해주기 -> Solution 1

 

# Solution 1 - DFS를 사용한 순열 생성

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

전체 리스트를 깊은 복사로 값을 복사한 새로운 리스트를 만들고 

값을 하나씩 빼주면서 새로운 리스트에 추가

리스트의 모든 값이 새로운 리스트에 삽입되었을 경우 결과리스트에 추가

 

# Solution 2 - itertools 모듈 사용

import itertools

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

itertools 모듈의 permutations 함수는 튜플 모음을 반환

---

# 객체 복사

파이썬에서는 모든 것이 객체이기 때문에 '=' 를 이용하면 객체의 참조가 복사되기 때문에 원래의 값을 변경하면 참조한 값도 변경된다.

리스트의 경우

a[:], a.copy() 를 이용하면 값을 복사한 다른 객체를 생성

복잡한 리스트의 경우 a.copy.deepcopy()를 이용해야 복잡하게 중첩된 리스트도 문제없이 복사된다.