중복 없는 순열

문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 단, 문자는 중복되어 나타날 수 없다.

다른 문제들과 마찬가지로, 작은 문제에서부터 확장하는 방식으로 생각해보자.

(1) 길이가 1인 문자열

(2) 길이가 2인 문자열

그렇다면 길이가 3인 문자열은 어떻게 만들 수 있을까?

배열의 모든 요소를 첫번째로 놓고 나머지 요소들의 순열을 덧붙이면된다.

문제가 훨씬 쉬워졌다!

그림으로 표현하자면 다음과 같다.

그럼 이제 코드로 표현을 해보자.

재귀 함수를 쓰면 아주 간단하게 표현할 수 있다. 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        def backtrack(start=0):
            
            if start == len(nums) :
                self.ans.append(nums[:])
            
            for i in range(start, len(nums)) :
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start+1)
                nums[start], nums[i] = nums[i], nums[start]
                
            
        self.ans = []
        backtrack()
        
        return self.ans

동작 과정

1. i번째 요소와 start 인덱스에 있는 요소의 위치를 바꿔준다.

여기서 start 인덱스에 있는 요소는 그림에서 표현한 빨간 문자를 가리킨다.

위의 수식에서 보자면 중괄호 안에 있는 a1, a2, a3을 나타낸다. 

2. start 인덱스 다음에 있는 나머지 요소들의 순열을 구한다.

위의 수식에서 보자면 중괄호 안에 있는 를 나타낸다.

3. (12번째 라인) 다음 순열에 영향을 주지 않도록 배열 요소들의 위치를 되돌려 놓는다.

4. 배열의 마지막 인덱스에 다다르면 ans 배열에 현재 nums를 추가한다.

수행시간

첫번째로 backtrack 함수가 실행될 때 배열의 길이(n)번 실행된다. 그 다음 함수에서는 n-1번, 그 다음에는 n-2번 실행되므로 순열 생성이 완성되는 시점에서 backtrack 함수는 n!번 호출될 것이다.

그림을 보면 말단 노드의 갯수는 n!개이고 루트에서 각 말단 노드까지의 거리는 n이다. 따라서 전체 노드(함수 호출)의 개수는 n*n!개를 넘지 못한다. 따라서 이 함수의 시간 복잡도는 이다.

문제 :

https://leetcode.com/problems/permutations/

참고 :

게일 라크만 맥도웰, 『Cracking the coding interview 6/E』, 프로그래밍인사이트(2012), 79쪽.