[leetcode 2024/02/15] 46. Permutations

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

python에서는 permutations를 library를 통해 이용할 수 있다. 

따라서 다음과 같이 한 줄이면 코드를 작성할 수 있다.

from itertools import permutations

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

from itertools import permutations

# 문자열 'ABC'의 모든 순열
for p in permutations('ABC'):
    print(p)

# 리스트 [1, 2, 3]의 길이가 2인 모든 순열
for p in permutations([1, 2, 3], 2):
    print(p)

위와 같이 permutations를 사용할 수 있다. 만약 인자 1개만 넣게 되면, 해당 인자의 length만큼의 순열을 return 해준다.

하지만 2번째 인자로 길이를 정해주게 되면, 해당 길이 만큼의 순열을 return 해준다.

위 코드에 대한 결과는 아래와 같다.

('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
...
(1, 2)
(1, 3)
(2, 1)
...

---

하지만, DFS를 이용해서도 풀어볼 것이다.

dfs(path, available) 로 값을 받는다.

path의 경우 연결지어지는 결과들을 의미하며, available의 경우 path에 다음으로 연결될 수 있는 후보군들을 의미한다.

 

nums= [1, 2, 3]으로 예시를 들어보자.

dfs([], nums) 로 값을 넘겨주어, available 에 [1, 2, 3] 이 저장되도록 한다.

 

for i in range(len(available)) 을 통해 시작한다.

i -> 0, 1, 2로 값이 바뀔 것이다.

 

dfs(path + [available[i]], available[:i] + available[i+1:]) 을 통해 path에 1, 2, 3을 넣어주고, 각각의 경우에 따라 넘겨주는 값을 제외한 나머지 list들 또한 넘겨주었다.

 

이런식으로 그래프가 구성되게 된다.

2. 코드

from itertools import permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(path, available):
            if not available:
                res.append(path)
                return
            for i in range(len(available)):
                dfs(path + [available[i]], available[:i] + available[i+1:])

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

 

+ 코드를 구성하면서 클로저를 알게되었다.

res의 경우, dfs에 인자로 넘겨주지 않았지만 dfs 함수 내에서 사용할 수 있다.

그 이유는 Python에서 함수가 다른 함수 내에서 정의되고 사용될 때, 내부 함수는 외부 함수의 변수를 "참조"할 수 있기 때문이다.

 

즉, 내부에서 외부의 것을 사용할 수 있다. 로 이해하면 된다. 또한 복사가 되는 것이 아니라, 실제로 그 변수에 변화를 줄 수 있다.

이러한 특성을 클로저; closure 라고 한다.