중복 있는 순열

 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 문자는 중복되어 나타날 수 있지만, 나열된 순열은 서로 중복되면 안 된다.

이 문제에서는 중복된 순열을 어떻게 찾아낼 것인가에 대하여 생각해보아야 한다.

단순히 모든 순열을 구한 후에 배열에 이 순열이 존재하지않으면 추가하는 방법으로 해결할 수 있다. 하지만 이 해결책은 최악의 경우 시간이 소요될 것이다.

그럼, 어떻게 접근해야할까?

먼저 작은 문제로 쪼개서 생각해보자.

'abca'라는 문자열이 주어졌다. 이 문자열의 순열을 구하려면 어떻게 해야할까?

중복 없는 순열을 풀때와 같이 문자열의 한 문자와 나머지 문자열의 순열을 구하고 이를 모두 합치면 된다.

수식으로 표현해보자면 다음과 같다.

하지만, 중복이 있는 문자열의 경우라면 빨간색으로 표시한 부분처럼 중복된 순열이 나타나게 될 것이다.

그럼 이 중복된 순열을 어떻게 처리해야할까?

hashset 을 사용하여 해당 문자가 이미 사용된 문자인지 아닌지 판별하면 되지않을까?

이 알고리즘을 코드로 표현해보면 다음과 같다.

중복된 문자가 많으면 많을수록 실행 시간은 줄어들 것이다.

class Solution:
    def helper(self, nums, start=0) :
        
        if start == len(nums)-1 :
            self.ans.append(nums[:])
            return
        
        used = set()
        
        for i in range(start, len(nums)) :
            
            if nums[i] not in used :
                
                used.add(nums[i])
                
                nums[i], nums[start] = nums[start], nums[i]
                self.helper(nums, start+1)
                nums[i], nums[start] = nums[start], nums[i]
        
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        
        if not nums :
            return []
        
        self.ans = []
        self.helper(nums)
        
        return self.ans

문제 :

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