leetcode medium : subsets II

Subsets II - LeetCode

Subsets II - LeetCode

 

지난 글 subsets에서 이어지는 문제같다

leetcode medium : subsets :: Keep your pace (tistory.com)

leetcode medium : subsets

 

 

숫자가 중복해서 주어질 수도 있다는 조건이 추가됐다.

그리고 결과리스트에는 중복이 있으면 안된다.

지난 문제에서 썼던 알고리즘으로 subset을 구하면 결과리스트에 중복되는 두 집합이 들어간다.

예를들어 [1,4,4]와 [4,1,4]가 결과리스트에 따로따로 들어갈수있다. 그러나 우리가 원하는 결과값은 서로다른 집합들이기 때문에 [1,4,4]와 [4,1,4]는 파이썬 타입으로는 리스트지만 마치 집합처럼 둘이 같은 값으로 인식되어야하며 둘중 하나만 추가되어야한다. [1,4,4]와 [4,1,4]가 같은 집합인지 구분하는 가장 쉬운 방법은 두 리스트를 정렬하고 같은 리스트인지 확인하는거다. [4,1,4]도 정렬하면 [1,4,4]가 되어버리니까 같은지 다른지 확인할 수 있다. 즉, 지난번에 사용했던 알고리즘을 수행하기 전에 nums 리스트를 먼저 sort해두자. 그리고 결과리스트에 값을 추가할 때 같은 값이 이미 결과셋에 있는지 검사하기만 하면된다. 저번 문제 솔루션에 단 두줄만 더 추가해서 이번 문제를 풀었다.

 

class Solution:
    def dfs(self, nums, index, path, result):
        if path not in result:
            result.append(path[:])
        
        if index == len(nums):
            return
        
        for i in range(index, len(nums)):
            self.dfs(nums, i + 1, path + [nums[i]], result)
    
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        self.dfs(nums, 0, [], result)
        return result

시간은 그럭저럭.. 근데 공간이 좀..? 더 optimal한 솔루션이 있나 고민해보자.

 

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

다른 사람이 작성한, 내가 쓴거랑 같은 알고리즘인데

 

훨씬 성능이 좋네.

function in function을 사용한거랑 recursive function의 인자가 더 적어서 그런가..

코드가 되게 간결하고 깔끔하다..

 

시간복잡도는 얼마나 될까?

알고리즘이랑 상관없이 각 요소가 있는 경우와 없는 경우를 다 탐색해야되니까 O(2^N)은 기본일거같다.

그리고 각 요소를 result리스트에 넣을 때 중복 체크하는게 +@로 더 나올거같은데 정확히 계산을 못하겠다 ㅠ

만약 중복이 없으면 result 리스트는 길이가 2^N이 되겠지? 그럼 result 리스트에 path가 있나없나 선형탐색하는건 평균적으로 O(2^N)은 될거고 O(2^N)의 조합의 각 경우마다 수행을 해야되니 O(2^N * 2^N)인가? 2 ^ 2N ?? 그럼 O(4 ^N)이야?;;;;;;; 이건 아닐거같은데.. 어렵구만

 

공간복잡도는 result list때문에 O(2^N)인게 확실하구만