Python Algorithm Q34

November 21, 2022

Q34 Permutations

Q

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Sample Input

Example 1

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2

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

Example 3

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

Constraints

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

1. My First Try

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

        # currentlist = 내가 현재 쌓아나가고 있는 list, leftlist = 빠져나가고 있는 list
        def recursion(_leftlist: List, _currentlist: List):
            # 직접 참조를 막기 위해 복사만 함
            leftlist = _leftlist[:]
            currentlist = _currentlist[:]

            if(len(leftlist) == 0):
                # print("ans appended")
                Ans.append(currentlist)
                return

            for N in leftlist:
                leftlist.remove(N)
                currentlist.append(N)
                recursion(leftlist, currentlist)

        recursion(nums, [])

        return Ans

이 코드를 넣고 돌려보면 얻을 수 있는 결과는 a = [1, 2, 3] 기준으로 [[1, 2, 3], [1, 3, 2]] 이다. 어? 코드를 보면 큰 문제가 없는데 출력은 첫 재귀에서 N = 1 일때만 나오는 것을 볼 수 있다. 왜 문제지 정말 오래 고민했었는데 답은 list는 어딘가에 저장된 value이기 때문에, 내가 그것을 변형하면 다음번 loop에도 영향을 미친다는 점이다. 그렇다. 바로 line 17, 18가 문제이다. 재귀를 할 때 핵심은 recursive한 process를 밟아도 초기 조건이 달라지지 않게 재귀 내부에서만 바뀌도록 해야한다는 것이다. 예를 들어, i += 1 -> dfs(i) 형태가 아니라 dfs(i+1) 형태로 넣어줘야지 기존의 변수에 변화가 생기지 않고 다음 재귀에 변화된 변수를 넣어줄 수 있다. 처음 시도 때는 이걸 몰라가지고 계속 루프가 중간에서 멈췄다…

2. My Own Solution

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

        def minus(list, int):
            templist = list[:]
            templist.remove(int)
            return templist

        # currentlist = 내가 현재 쌓아나가고 있는 list, leftlist = 빠져나가고 있는 list
        def recursion(_leftlist: List, _currentlist: List):
            # 직접 참조를 막기 위해 복사만 함
            leftlist = _leftlist[:]
            currentlist = _currentlist[:]

            if(len(leftlist) == 0):
                # print("ans appended")
                Ans.append(currentlist)
                return

            for N in leftlist:
                recursion(minus(leftlist,N), currentlist+[N])
            
        if(nums):
            recursion(nums, [])

        return Ans

# test set
a = Solution()
b = [1, 2, 3]
a.permute(b)

1번 풀이에서 내가 발견한 문제점을 고쳐서 제출한 풀이다. 결과는 대성공!! line 22를 보면 기존에 위에서 적용했던 append와 remove를 따로 빼서 재귀에 넣는 그 순간에 계산하도록 해서 변수 자체에는 변화가 없도록 했다. recursion의 두번째 인수, currenelist + [N]를 보면 python lists는 편리하게 덧셈 연산을 지원하기 때문에 append를 쓰지 않아도 편하게 element를 추가할 수 있다. 하지만 - 는 지원하지 않기 때문에, minus라는 function을 위에 구현해서 대신 연산을 했다. 물론 minus 함수 안에서도 list에 직접적으로 변화를 주면 안되기 때문에 철저하게 리스트 그 자체를 참조하지 않게 [:] 형태로 복사해서 가져왔다. 통과하기는 했는데 이렇게 제출한 코드를 남들과 비교해보니까 time이랑 memory 둘다 개많이 잡아먹더라… 조금 아쉬운 결과였던 것 같다. 다만 답 안보고 진짜 혼자 풀어서 좀 뿌듯함 ㅎㅎ

3. Given Solution #1

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

책에 있던 풀이이다. 여기서 참 인상적이었던 점은 prev_elements를 시점에 맞에 적절하게 이용한다는 점이다. 내가 코드를 짤 때 좀 복잡했던 점은 recursive function의 인수로 left_lest, current_list로 두 가지 list를 받았다. 남아있는 숫자들을 저장하고 있는 left_list와 내가 숫자를 삽입해나가는 current_list를 동시에 인수로 받다보니 두 인수 모두 다 도중에 변형되지 않게 신경을 써야 했다. 근데 여기서 line 14를 보면 정말 기가 막힌다. 여기서 딱 prev를 정의해놓고, 다음 재귀를 시작한다. 그럼 자연스럽게 다음 재귀에서는 이 prev_element를 이용한 재귀를 반복한다! 노트에 정리한 사진을 참고하자.

보면 재귀에 진입하기 전에 앞에까지 쌓아놓고, 재귀 끝나자마자 다시 pop을 이용해서 빼버린다. 정말 깔끔하고 대단한 풀이인 것 같다.

3. Given Solution #2

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

파이썬에 이미 예쁘고 깔끔하게 구현되어있는 라이브러리를 이용한 풀이이다. itertools 모듈인데, 효율적으로 설계된 C라이브러리라 속도도 빠르고 최적화가 잘 되어있다고 한다. 라이브러리 부자다운 파이썬스러운 방식.

참고사항

https://crackerjacks.tistory.com/14 위에서 언급했던 list의 copy에 대해 자세히 다룬 자료이다. list, set, dictionary는 mutable한 variable이기 때문에 리스트 슬라이싱, .copy() 등의 방식이 아니라 직접 할당을 할 경우 객체 자체에 대한 참조가 되어 A에서는 바꾸지 않았지만 B에서 바꿨으면 A도 동일하게 바뀌는 경우가 발생한다. 보통 리스트 복사에서 이를 방지하는 가장 좋은 방법은 리스트 슬라이싱 a = b[:] 이다. 많이 애용하자.

Overall Review

스스로 풀었다는 점에서 일단 뿌듯하다! 다만 주어진 풀이에서 보여준 방식이 굉장히 깔끔하기 때문에 다음에 풀이를 짤 때는 재귀에 들어가는 시점을 잘 파악하고 설계하면 보다 깔끔한 답안을 낼 수 있을 것 같다.

Hyuntae H