[2024] day 145. leetcode 2597. The Number of Beautiful Subsets

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 23일 (목)
Leetcode daily problem

2597. The Number of Beautiful Subsets

https://leetcode.com/problems/the-number-of-beautiful-subsets/?envType=daily-question&envId=2024-05-23

Problem

양의 정수로 구성된 배열 num과 양의 정수 k가 제공됩니다.
nums의 하위 집합은 k와 동일한 절대값 차이를 갖는 두 개의 정수를 포함하지 않는 경우 "beautiful" 하다고 판단한다.
nums 배열의 비어 있지 않은 "beautiful한 부분 집합의 수"를 반환한다.
nums의 하위 집합은 nums에서 일부(없을 수도 있음) 요소를 삭제하여 얻을 수 있는 배열이다. 삭제하기 위해 선택한 인덱스가 다른 경우에만 두 하위 집합이 다르다.

Solution

backtracking

backtracking을 이용해서 하위 집합을 만들기 위해 각 숫자를 하위 집합에 포함할지 여부를 결정한다. 이렇게 하면 두 개의 경로가 생성된다. 하나는 하위 집합에 숫자를 추가하는 경로이고 다른 하나는 추가하지 않는 경로이다.

크기가 n인 배열의 경우 각 요소는 포함되거나 제외될 수 있으므로 최대 (2^n)개의 하위 집합이 생성될 수 있다. 인덱스 i에서 우리는 두 개의 하위 집합을 만드는데, 하나는 현재의 각 숫자를 포함하는 것, 다른 하나는 포함되지 않는것이다. 우리가 생성하는 하위 집합 중 하나는 빈 하위 집합이 될 것이므로 마지막에 1을 빼서 제외한다.

"beautiful"한 하위 집합을 보장하려면 이전에 nums[i] + k 또는 nums[i] - k가 사용되지 않았는지 확인해야 한다. 우리는 본 숫자를 추적하는 빈도를 저장하는 map을 사용한다. nums[i]를 추가하기 전에 nums[i] + k도 nums[i] - k도 맵에 없는지 확인한다. 둘 다 없으면 하위 집합에 nums[i]를 추가한다.

하지만 현재 인덱스 i 이전에 배열에 더 큰 요소가 없었다는 것을 확인한다면 nums[i] - k의 여부만 확인하면 된다. backtracking을 이용한 재귀를 수행하기 전에 배열을 정렬해서 nums[i] + k를 확인하는 로직을 없애서 줄인다.
이렇게 하면 nums[i] - k만 확인하면 되므로 탐색의 수가 줄어 들게 된다.

Code

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        
        freq_map = defaultdict(int)
        nums.sort()
        return self.backtracking(nums, k, freq_map, 0) - 1
    
    def backtracking(self, nums, differ, freq_map, idx):
        if idx == len(nums):
            return 1
        
        
        total_cnt = self.backtracking(nums,differ,freq_map,idx+1)
        
        if nums[idx] - differ not in freq_map:
            freq_map[nums[idx]] +=1
            
            total_cnt += self.backtracking(nums,differ,freq_map,idx+1)
            freq_map[nums[idx]] -= 1
            
            if freq_map[nums[idx]] == 0:
                del freq_map[nums[idx]]
                
                
        return total_cnt

beautifulSubsets

• 요소의 빈도를 추적하기 위해 freq_map이라는 map 생성
  -숫자 배열을 정렬
• nums, k, freqMap 및 0 매개변수를 사용하여 countBeautifulSubsets 메서드를 호출
• 결과에서 1을 빼고 반환합니다.

countBeautifulSubsets

• nums(주어진 배열), 차이(k로 제공됨), freq_map(요소 빈도를 추적하기 위한 맵) 및 i(고려 중인 현재 요소의 인덱스)의 네 가지 매개 변수를 사용함
• 기본 사례: i가 배열 nums의 길이와 같으면 1을 반환합니다(크기 1의 하위 집합을 나타냄).
• i + 1을 사용하여 countBeautifulSubsets를 재귀적으로 호출하여 현재 요소를 포함하지 않고 하위 집합의 개수를 계산함
  - 조건을 위반하지 않고 현재 요소 nums[i]를 포함하는 것이 가능한지 확인
  0 freqMap에 nums[i] - k가 없으면 차분 조건을 만족한다는 의미
  - freqMap에서 가져온 대로 nums[i]를 표시
• i + 1을 사용하여 countBeautifulSubsets를 재귀적으로 호출하여 현재 요소를 포함한 하위 집합의 개수를 계산
• 역추적: freqMap에서 nums[i]를 가져오지 않은 것으로 표시
• 개수가 0이 되면 freqMap에서 nums[i]를 제거
• beautiful 한 하위 집합의 총 개수를 반환함

Complexicity

시간 복잡도

생성된 하위 집합의 수에 따라 결정되는데, 위 알고리즘은 입력 배열의 가능한 모든 하위 집합을 탐색하므로 크기 배열에서 생성할 수 있는 하위 집합의 최대 수는 2^n 이다.
배열을 처음 정렬하는 경우에 O(nlogn)이 소요되지만 따라서 전체 시간복잡도는 하위 집합 생성이 소요되는 O(2^n) 이다. 배열을 제자리에 정렬할 때 약간의 추가 공간이 사용된다는 점에 유의하세요. 정렬 알고리즘의 공간 복잡도는 프로그래밍 언어에 따라 다릅니다.

공간 복잡도

배열을 정렬할 때 약간의 추가 공간이 사용된다.
Python에서 정렬 방법은 병합 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)을 조합한 팀 정렬(Tim Sort) 알고리즘을 사용하여 목록을 정렬하는데, O(n)에 도달한다.