2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 5월 23일 (목)
Leetcode daily problem
2597. The Number of Beautiful Subsets
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_cntbeautifulSubsets
- 요소의 빈도를 추적하기 위해 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)에 도달한다.
