leetcode.com 46. Permutations

문제 링크: https://leetcode.com/problems/permutations/description/

파이썬 소스: https://bit.ly/43TvJbM

 

 순열(permutation)을 구현해 보는 문제입니다. 가장 간단한 풀이법은 파이썬에서 제공하는 permutations를 import해서 코딩하는 방법입니다. 하지만, 문제 출제의도는 직접 순열을 코딩해보라는 것이기 때문에, 파이썬에서 제공하는 permutations을 사용하지 않고, 직접 코딩해 보도록 하겠습니다.

 코딩해보기에 앞서서, 순열(permutation)에 대해서 알아보겠습니다.

1. N개의 원소가 주어집니다.

2. N개의 원소 중에서, L개를 선택할 수 있으며, L의 범위는 1<= L <= N 입니다.

3. L개를 선택할 때, 순서를 고려하여, 선택해서 나열해야 합니다.

순열을 공부할 때, 3번이 가장 난해한 문장입니다. ‘순서를 고려해서 나열한다’…?

 

N개의 원소 1, 2, 3 이 주어지고, L이 2라고 가정하고, 풀이해 보겠습니다.

1을 먼저 선택합니다. [1, ]

순서를 고려해야 하기 때문에, 첫번째 자리에 1이 오는 것을 선택한 것입니다.

이제, 두번째 자리에 올 숫자를 선택하는 일이 남았습니다.

2를 선택할 수도, 3을 선택할 수도 있습니다.

따라서, [1, 2], [1, 3] 모두 [1,2,3]의 길이 2인 순열에 해당합니다.

여기까지 풀이하면, 첫번째 자리에 1이 오는 것은 모두 찾았습니다. 하지만, 아직 모든 순열을 찾은 것은 아닙니다. 왜냐하면, 첫번째 자리에, 2가 올 수 도, 3이 올 수도 있기 때문입니다.

2를 첫번째 자리에 선택합니다. [2, ]

1은 아직까지 두번째 자리에 온 적이 없었죠, 두번째 자리에 배치합니다. [2, 1]

3도 두번째 자리에 배치합니다. [2, 3]

[2, 1], [2, 3] 모두 [1,2,3]의 길이 2인 순열에 해당합니다. 여기까지 찾은 모둔 순열을 나열에 보면 아래와 같습니다.

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

여기서 눈 여겨 볼 부분이, 3입니다. [1, 3]에서 3은 두번째 자리에 있었지만, 첫번째 자리에 있는 수가 1, 2로 서로 다르기 때문에, [1, 3], [2, 3]은 서로 다른 순열입니다. 이와 마찬가지로, [1, 2], [2, 1]도 서로 다른 순열입니다.

이 부분이 앞에서 설명한 3번 ‘3. L개를 선택할 때, 순서를 고려하여, 선택해서 나열해야 합니다.’ 의 의미입니다. 순열을 공부할 때 가장 헷갈리는 부분이기도 합니다.

정리하면, 숫자와 순서가 모두 같은 순열만 같은 것 이구요, 하나의 숫자라도 다른 순서에 있다면 서로 다른 순열이 됩니다.

 

 이제 순열(permutation)에 대해서 알아보았으니, 코딩을 시작해 보겠습니다.

answer: List = []

순열이 만들어지면, 저장할 answer 리스트가 필요하구요.

nums.sort()

숫자가 들어 잇는 리스트 nums는 꼭 정렬할 필요는 없지만, 디버깅할 때, 작은 숫자가 앞에 오는 것이 조금 편하기 때문에, 정렬을 해줍니다.

visited: List[bool] = [False for _ in range(len(nums))]

순열은 숫자와 숫자의 순서를 고려해야 하는 것이지, 그렇다고 해서 숫자가 중복해서 나오는 것은 순열이 아닙니다. 따라서, visited 리스트를 사용해서, 현재까지 방문한 숫자는 순열에서 제외될 것입니다.

 

def rec(nums, depth_crnt, depth_mx, pathes, answer: List):

재귀함수를 사용해서 순열을 구하겠습니다. 따라서, depth가 필요합니다. 앞에서 설명한 순열의 길이 L이 depth에 해당합니다. 다만 첫번째 수, 두번째 수 등을 의미는, depth_crnt와, 순열의 길이를 의미하는 L은 depth_mx, 2개로 변수로 나누겠습니다.

 

재귀함수는 처음 아래와 같이 호출됩니다.

rec(nums, 0, len(nums), [], answer)

이 문제에서는 주어진 nums리스트의 길이에 해당하는 순열을 찾기 때문에 depth_mx는 len(nums)가 됩니다. 최초 호출이기 때문에 depth_crnt는 0이 되구요. 마찬가지로 첫번째 숫자로 없는 상태이기 때문에, pathes리스트도 빈 리스트 []가 됩니다.

 

def rec(nums, depth_crnt, depth_mx, pathes, answer: List):     if depth_crnt == depth_mx:         answer.append(pathes)         return

재귀함수 이기 때문에 재귀호출을 멈추는 조건, stop condition부터 알아보면, depth_crnt와 depth_max가 같아지면 재귀호출을 멈추는 것입니다. L 길이만큼 pathes에 숫자가 채워졌기 때문에, 하나의 순열을 찾은 것입니다. 리스트 answers에 pathess를 넣어주고 다음 순열을 찾기 위해서 리턴합니다.

 

for idx in range(len(nums)):     if not visited[idx]:         visited[idx] = True         rec(nums, depth_crnt +1, depth_mx, pathes + [nums[idx]], answer)         visited[idx] = False

 이제 for루프에서 각 위치에 들어갈 숫자를 찾아 보겠습니다.

앞에서 설명할 때, 첫번째 숫자, 두번째 숫자라는 표현을 사용을 사용했습니다. 코드에서는 첫번째 숫자는 depth_crnt +1 == 1일 때 찾게 되구요, 두번째 숫자는 depth_crtn + 1 == 2일 때 찾게 됩니다.

 재귀 함수가 한번씩 더 호출될 때 마다, depth_crnt에 +1을 해서, 다음번 순서에 올 숫자를 찾게 됩니다.

 여기서 visited[idx] = True로 표시를 해두고, 같은 숫자가 중복해서 pathes리스트에 추가되는 것을 막는 것입니다. 재귀함수가 리턴이 되면, visited[idx] = False로 표시를 합니다. 같은 숫자여도 다른 순서에는 배치될 수 있기 때문입니다.

 

 앞에서 설명한 내용을 모두 종합해서 구현하면 아래와 같이 코딩할 수 있습니다.

from typing import List class Solution:     def permute(self, nums: List[int]) -> List[List[int]]:         answer: List = []         nums.sort()         visited: List[bool] = [False for _ in range(len(nums))]         def rec(nums, depth_crnt, depth_mx, pathes, answer: List):             if depth_crnt == depth_mx:                 answer.append(pathes)                 return             for idx in range(len(nums)):                 if not visited[idx]:                     visited[idx] = True                     rec(nums, depth_crnt +1, depth_mx, pathes + [nums[idx]], answer)                     visited[idx] = False         rec(nums, 0, len(nums), [], answer)         return answer

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul