미소를뿌리는감자의 코딩
[leetcode 2024/02/15] 46. Permutations 본문
https://leetcode.com/problems/permutations/description/
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 라고 한다.
'코딩 테스트 > leetcode' 카테고리의 다른 글
[leetcode 2024/02/17] 700. Search in a Binary Search Tree (0) | 2024.02.17 |
---|---|
[leetcode 2024/02/15] 77. Combinations (1) | 2024.02.15 |
[leetcode 2024/02/15] 17. Letter Combinations of a Phone Number (1) | 2024.02.15 |
[leetcode 2024/02/13] 328. Odd Even Linked List (0) | 2024.02.13 |
[leetcode 2024/02/13] 21. Merge Two Sorted Lists (0) | 2024.02.13 |