[리트코드] 46. 순열 (Python)

Permutations - LeetCode

문제

배열을 입력받고 가능한 모든 수열을 출력해라

과정

1. 순열이란 모든 가능한 경우를 그래프 형태로 나열한 결과이다.
2. 즉, 백트래킹을 이용하여 문제를 풀어준다.
3. 백트래킹(backtracking)이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다.

 

입력

[1,2,3]

출력

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

풀이

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []

        def dfs(next, prev):
            if not prev:
                return result.append(next)
            for i, num in enumerate(prev):
                dfs(next + [num], prev[:i] + prev[i+1:])

        dfs([], nums)
        return result

 

한 줄씩 코드 해석해보기

result = []

• 결과를 출력할 리스트를 생성한다.

def dfs(next, prev):
    if not prev:
        return result.append(next)

• 백트래킹 함수 dfs를 만들어준다. (next는 결과를 저장할 리스트이고, prev는 아직 저장되지 않은 리스트값이다.)
• prev 리스트에 값이 없다면 순열을 다 돈것이므로 result 에 append해준후 반환한다.

for i, num in enumerate(prev):
    dfs(next + [num], prev[:i] + prev[i+1:])

• prev 리스트를 enumerate를 활용해 인덱스값과 각 숫자들을 받아온다.
• next 리스트에 새로 받아오는 값을 가지고 새로운 리스트를 만들어 추가해준다.
• 그 다음 이전 값에서 i번째 값을 삭제해 줘야하기 때문에 i의 이전 값고 i+1의 다음값을 합쳐주면서 삭제해준다.

dfs([], nums)
return result

• 처음 dfs함수에 들어가는 값은 next에는 빈 리스트 prev에는 입력받은 nums가 들어가게 된다.
• 결과를 리턴해준다.

 

한 줄 풀이

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

• itretools.permutations(list) : list의 값들을 모든 가능한 순서, 반복되는 요소 없이 반환한다. 즉, 순열을 만들어 준다.