[백트래킹] LeetCode 46. Permutations
PS는 꾸준함입니다.
오늘은 순열을 구하는 대표적인 문제인LeetCode 46번 Permutations문제를 풀어보았습니다.
이 문제는 문제 자체는 간단해 보이지만, 재귀와 백트래킹의 핵심 개념을 완벽히 이해하고 구현해보기에 좋은 연습문제입니다.
1. 문제: LeetCode 46. Permutations
- 단계: Medium
- 주제:
- 출처: https://leetcode.com/problems/permutations/description/
문제
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
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.
2. 문제 파악
이 문제는 순열 문제입니다. 주어진 nums 배열에 있는 요소들을 가지고 순열을 만드는 문제입니다.
nums배열의 요소들은 서로 다르다고 합니다.
제약 조건을 살펴보겠습니다.
- Input:
- nums 배열의 길이는 1이상 6이하입니다. → 이 크기가 시간 복잡도에 영향을 줄 것으로 보입니다. (O(n!)) , n == len(nums)
- nums배열의 요소 값의 크기는 -10 이상 10이하입니다.
- 모든 요소들은 정수이며 서로 다릅니다.
- output:
- 모든 순열을 반환해야 합니다. 즉, 이중 리스트!
3. 접근 방법
흔히 알고 있는 python의 itertools 라이브러리를 활용해서 구할 수 있습니다.
또한, 재귀로도 풀 수 있습니다.
예를 들어, 생각해 봅시다.
nums = [1, 2, 3]이 있습니다. 이를 통해 생성할 수 있는 순열은 다음과 같습니다.
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 이렇게 총 6개가 나옵니다.
이렇게 나오는 경우를 State Space Tree로도 그려볼 수 있습니다. 주의해야 할 점은 순열은 순서를 본다는 것입니다.
즉 [1, 2, 3] 과 [1, 3, 2] 2와 3의 위치가 바뀌었지만 서로 다른 순열이라는 것입니다.
그림은 다음과 같습니다:
1에서 시작한다면 2, 3, / 3, 2 이렇게 만들수 있습니다.
그런데 1에서 2, 2에서 3이렇게 다 도착을 해서 순열을 만들었다면, 1에서 3, 3에서 2로 가기 위해 다시 돌아가야 합니다. 그렇기 때문에 백트래킹이 사용됩니다.
백트래킹의 기저 조건은 순열의 길이가 주어진 nums와 같아지면 하나의 순열이 완성되는 것입니다. 그렇게 되면 만들어진 순열을 저장하는 것이죠!
[1, 2, 3]이 완성 되었으니, 이제 2 와 3을 빠져나와야 합니다. 그렇기 때문에 pop()과정을 거쳐서 백트래킹을 진행합니다.
여기서 주의할 점은, 순열을 만들 때 숫자가 중복 되어서는 안됩니다.
따라서, 만들어지는 순열에 이전 숫자가 들어있는지 없는지를 판단하고 없을 시에만 위와 같은 과정을 거쳐야 합니다.
1로 시작하는 순열이 끝나면 1도 pop이 되겠죠?
그럼 다음 숫자 2로 1에서 했던 과정을 다 거치게 됩니다.
그래서 최종적으로 다음과 같은 결과가 나오게 됩니다.
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
이제 이것을 기반으로 코드 구현을 하면 아래과 같습니다.
코드 구현
# <https://leetcode.com/problems/permutations/>
# <https://leetcode.com/problems/word-search/submissions/1563717945>
# 시간 복잡도: O(N!)
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
def dfs(curr):
# 1. base case
if len(curr) == len(nums):
ans.append(curr[:])
return
for num in nums:
if num not in curr:
curr.append(num)
dfs(curr)
curr.pop()
dfs([])
return ans
# <https://leetcode.com/problems/permutations/submissions/1565715845>
from itertools import permutations
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
return list(map(list, permutations(nums)))
4. 배우게 된 점
- 순열은 완전탐색(Brute-force) 의 대표 예시로, DFS + 백트래킹으로 풀 수 있습니다.
- visited 배열을 사용하면 in 연산보다 빠르게 조건을 확인할 수 있어 실전 코딩 테스트에 유리합니다.
- itertools는 매우 유용하지만, 원리를 알고 구현하는 연습이 꼭 필요합니다.
- 백트래킹의 핵심은 탐색 후 원상 복구라는 점! append → dfs → pop 순서가 매우 중요합니다.
추가!!
앞서 작성한 재귀코드에서 조금 더 시간 복잡도를 줄일 수 있습니다.
코드는 아래와 같습니다:
# 2. 재귀 (in 연산자 사용 안하기)
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
used = [False] * (len(nums))
def dfs(curr):
# 1. base case
if len(curr) == len(nums):
ans.append(curr[:])
return
for i in range(len(nums)):
if not used[i]:
used[i] = True
curr.append(nums[i])
dfs(curr)
curr.pop()
used[i] = False
dfs([])
return ans
이 코드가 메모리는 쓰지만 시간 복잡도 상으로 효율적이며, 범용성이 높을것 같습니다. 이 코드를 기반으로 반복적인 훈련이 필요하다고 생각합니다!
마무리
이 문제를 통해 다시 한 번 백트래킹의 기초를 정리하고 실전 감각을 익힐 수 있었습니다.
문제를 반복적으로 풀며, 손에 익히는 것이 중요하다는 걸 다시 느꼈습니다.
저의 블로그를 보시면 백준의 N과 M 시리즈 문제들을 보시면 더욱 이해가 잘 될 것입니다..!
🌱 다음 목표는 LeetCode의 조합 문제입니다.