글 제목에서부터 알 수 있듯이,
순열을 구하는 문제이다.
자세한 내용은 여기에서 볼 수 있다.
풀이 방법은 총 두 가지를 소개할 예정이다.
하나는 DFS, 다른 하나는 반복문을 사용한 방법이다.
첫 번째 방법 - DFS
아마 많이들 생각할 방법일 것 같다.
순열을 만들 숫자 N개를 담은 리스트를 nums이라 했을 때,
N!개의 원소를 담은 리스트를 최종 리턴해야 하니까 말이다.
코드는 Discuss의 글에서 찾았고, 아래와 같다.
def permute(self, nums):
res = []
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
if not nums:
res.append(path)
for i in range(len(nums)):
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
핵심이 되는 dfs 메서드를 보면,
문제에서 주어지는 숫자들의 리스트인 nums의 원소들을 돌며
하나의 원소를 빼서 path에 붙여
또다시 dfs 메서드를 실행한다.
잘 이해가 안간다면
위의 discuss 링크의 글에서 누군가가 작성한 Visualization 댓글을 보면 좋다.
아래처럼 코드의 진행 상황에 맞추어 주요 변수들의 값을 적어놓았다.
dfs(nums = [1, 2, 3] , path = [] , result = [] )
|____ dfs(nums = [2, 3] , path = [1] , result = [] )
| |___dfs(nums = [3] , path = [1, 2] , result = [] )
| | |___dfs(nums = [] , path = [1, 2, 3] , result = [[1, 2, 3]] ) # added a new permutation to the result
| |___dfs(nums = [2] , path = [1, 3] , result = [[1, 2, 3]] )
| |___dfs(nums = [] , path = [1, 3, 2] , result = [[1, 2, 3], [1, 3, 2]] ) # added a new permutation to the result
|____ dfs(nums = [1, 3] , path = [2] , result = [[1, 2, 3], [1, 3, 2]] )
| |___dfs(nums = [3] , path = [2, 1] , result = [[1, 2, 3], [1, 3, 2]] )
| | |___dfs(nums = [] , path = [2, 1, 3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]] ) # added a new permutation to the result
| |___dfs(nums = [1] , path = [2, 3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]] )
| |___dfs(nums = [] , path = [2, 3, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] ) # added a new permutation to the result
|____ dfs(nums = [1, 2] , path = [3] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] )
|___dfs(nums = [2] , path = [3, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]] )
| |___dfs(nums = [] , path = [3, 1, 2] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]] ) # added a new permutation to the result
|___dfs(nums = [1] , path = [3, 2] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]] )
|___dfs(nums = [] , path = [3, 2, 1] , result = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ) # added a new permutation to the result
결과는 아래에서 소개할 두번째 방법보다 좀 덜 빠르지만,
그래도 나름 준수한 편이다.
두 번째 방법 - 반복문
이 방법 역시 Discuss 중 하나에서 찾았다.
코드는 아래와 같다.
class Solution(object):
def permute(self, nums):
def swap(i, j, nums):
new_nums = list(nums)
new_nums[i], new_nums[j] = new_nums[j], new_nums[i]
return new_nums
result = [nums,]
for i in range(len(nums)-1):
for one in result[:]:
for j in range(i+1, len(nums)):
result.append(swap(i, j, one))
return result
사실 dfs라는 메서드를 따로 두지 않고
dfs를 반복문으로 직접 구현한 것이라고 봐도 될 것 같다.
알고리즘은 꽤 간단하지만, 주의해야 할 곳은
두 번째 for 문의 result[:] 이다.
[:]에 대해 모른다면 Python의 얕은 복사(Shallow Copy)에 대해 알아보면 된다.
여기의 글만 봐도 충분히 이해된다.
어쨋든, result라는 리스트를 복사해서 사용하는 이유를 확인해보려면
반복문 중간 중간 result의 값을 찍어보면 알 수 있다.
만약 copy 하지 않고 사용하게 된다면,
같은 result를 계속 반복하게 되어 무한 루프에 빠지게 된다.
이 discuss 글의 댓글을 보면,
leetcode에서 변태 수준으로 Python을 사용하여
1-2줄 짜리 코드를 올리시는 분께서 피드백 준 것이 있다.
해당 피드백을 적용하면 훨씬 코드가 깔끔해진다.
이 코드의 실행 결과는 아래와 같다.
굉장히 빠른 속도이다.
끝!
