문제
https://leetcode.com/problems/permutations/
주어진 배열의 순열을 구하자.
풀이 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)
'알고리즘 > 파이썬 알고리즘 인터뷰' 카테고리의 다른 글
[LeetCode] 77. Combinations (그래프) (0) | 2022.06.16 |
---|---|
[LeetCode] 17. Letter Combinations of a Phone Number (그래프) (0) | 2022.06.16 |
[LeetCode] 200. Number of Islands (그래프) (0) | 2022.06.15 |
슬라이딩 윈도우 (0) | 2022.06.07 |
[LeetCode] 49. Group Anagrams (문자열 조작) (0) | 2022.06.02 |