[2024] day 175. Leetcode 1248. Count Number of Nice Subarrays

gunny·2024년 6월 26일

leetcode 1248. Count Number of Nice Subarrays leetcode 1248. Count Number of Nice Subarrays python

코딩테스트

목록 보기

489/530

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

2024년 6월 22일 (토)
Leetcode daily problem

1248. Count Number of Nice Subarrays

https://leetcode.com/problems/count-number-of-nice-subarrays/?envType=daily-question&envId=2024-06-22

Problem

정수 배열 nums와 정수 k가 주어진다. 이 때 연속된 k개의 홀수로 이루어진 배열을 'nice'라고 할 때, nice한 부분 배열의 수를 반환한다.

Solution

Hashing or Sliding window

[1] Hashing

Hashing으로 푸는 방법과 sliding window 로 푸는 방법이 있는데, 먼저 Hashing으로 접근하는 방법으로 특정 개수의 홀수 요소를 포함하는 부분 배열의 수를 찾아야 하므로, 요소의 숫자 값을 홀수는 1, 짝수는 0으로 대체한다.
배열 내에서 합이 원하는 홀수 요소의 개수와 같은 요소들의 시퀀스를 식별하기 위해서 누적합을 사용해, 새로 고려되는 모든 부분 배열의 요소 합을 계산하는 대신 두 인덱스 사이의 요소의 합을 계산하는 방식으로 배열 내 '두 인덱스 사이의 홀수 개수'를 계산한다.
해시맵을 사용해 각 인덱스까지의 prefix sum을 key로 발생 빈도를 값으로 저장한다.
배열 nums를 순회하며 각 요소까지의 prefix sum을 계산하고 해시맵에 기록하면서, 특정 합이 다시 나타나면 해당 합의 빈도를 증가시키고 각 합이 나타날 떄마다 sum-k가 이전에 몇 번 나타났는지 찾아보고 그 횟수만큼 부분 배열의 수를 증가시킨다.

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        curSum, subArray = 0, 0 
        prefix_sum = {curSum : 1}
        
        for i in range(len(nums)):
            curSum += nums[i] %2
            if curSum -k in prefix_sum:
                subArray = subArray + prefix_sum[curSum-k]
                
            prefix_sum[curSum] = prefix_sum.get(curSum,0)+1
            
        return subArray

nums의 배열을 한번 순회하고, 각 반복마다는 상수 시간의 연산을 수행하므로 시간복잡도 O(n)이다. 여기서의 공간복잡도는 prefix_sum의 크기에 결정되는데 최악인 경우 curSum의 모든 값을 저장할 수 있다. curSum은 배열의 길이 n에 따라 제한되므로 최종 공간복잡도 O(n) 이 소요된다.

[2] Sliding window (queue 사용)

슬라이딩 윈도우 패턴은 조건이 만족될 때 까지 오른쪽에서 요소를 추가하고, 만족하지 않으면 왼쪽에 요소를 제거하면서 윈도우를 조정해나간다.

nums 배열에 음수가 포함되어 있으면 슬라이딩 윈도우 접근은 효과적으로 작동하지 않을 수 있는데, 음수가 포함된 경우 윈도우를 확장하면 합이 감소할 수 있어 최적의 subarray를 찾는 과정이 조금 복잡해진다.
음수가 아닐 경우 윈도우를 확장하면서 subarray를 찾는 것이 더 수월하다.

즉 이때는 'k'개의 홀수 요소를 포함하고 홀수 요소로 시작하고 끝나는 모든 고유한 윈도우를 찾아간다.

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        ans = 0
        queue = deque()
        gap = -1
        odd_pos = -1
        
        for i in range(len(nums)):
            if nums[i]%2==1:
                queue.append(i)
                
            if len(queue) > k :
                odd_pos = queue.popleft()
                
            if len(queue) == k:
                gap = queue[0] - odd_pos
                ans += gap
                
        return ans

[3] sliding window + queue (space optimizer)

위에서 0의 빈도를 필요로 하기 떄문에 추가적인 O(n)을 사용하지 않고 이 값을 계산해서 알고리즘을 최적화한다.

윈도우의 모든 가능한 끝점을 반복하면서 qsize라는 정수를 사용해 홀수 값의 개수를 추적한다. qsize가 k에 도달하면 시작 포인터를 조정하여 부분 배열의 시작 부분에서 홀수 값을 만날 때 까지 짝수 값을 건너뛴다.

시작 포인터로 덮인 짝수 값을 initialGap으로 계산해 답에 추가하고, 이후 모든 짝수값에 대해 이 값을 답으로 추가한다.

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        ans = 0
        qsize = 0
        start = 0
        gap = 0
        
        for end in range(len(nums)):
            if nums[end]%2==1:
                qsize +=1
                
            if qsize == k:
                gap = 0
                
                while qsize==k:
                    qsize-= nums[start]%2
                    gap += 1
                    start +=1
            
            ans += gap
            
        return ans

위 코드는 for, while 루프가 있는데 외부 for 루프는 nums 배열을 순회하므로 O(n), 내부 while 루프는 qsize와 k가 같을 때만 실행되고, 각 요소에 대해 최대 한 번만 실행되므로 전체적으로 O(n)이다.
즉 시간 복잡도는 O(n) 이다.
위에서 추가적으로 사용되는 것은 상수를 업데이트하는 변수이므로 전체 공간 복잡도는 O(1) 이다.

Code

가장 이해가 잘되는 부분은 역시 Hashing ~!

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cur_sum = 0
        ans = 0
        prefix_sum = {cur_sum : 1}
        
        for i in range(len(nums)):
            cur_sum += nums[i] % 2
            
            if cur_sum-k in prefix_sum:
                ans += prefix_sum[cur_sum-k]
                
            prefix_sum[cur_sum] = prefix_sum.get(cur_sum,0)+1
            
        return ans