[2024] day 75. Leetcode 930. Binary Subarrays With Sum

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

2024년 3월 14일 (목)
Leetcode daily problem

hhttps://leetcode.com/problems/binary-subarrays-with-sum/description/

Problem

binary 배열(0과 1로만 구성 배열)과 정수 goal이 주어질 때,
연속된 부분집합의 합이 goal과 동일할 때의 경우의 수를 반환한다.

Solution

Cumulative sum

해당 문제는 누적합과 해시맵을 사용하거나 two pointer를 사용하는 방법으로 해결할 수 있다. 먼저 나는 누적합과 해시맵을 사용해서 문제를 해결했다.

각 배열의 요소까지 누적합을 구하면서 해시맵을 업데이트 해 나가는데,
요소마다 현재까지의 누적합에서 goal(타겟)을 뺀 값이 해시맵에 있는지 확인한다.
이를 통해서 이전에 나온 누적합과 현재 누적합의 차이가 goal과 일치하는 경우가 몇 번 나오는지 파악할 수 있다.

Code

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        cnt = {0:1}
        curSum = 0
        totalSum = 0

        for num in nums:
            curSum += num
            if curSum-goal in cnt:
                totalSum += cnt[curSum-goal]
            cnt[curSum] = 1+cnt.get(curSum,0)

        return totalSum

Complexicity

시간 복잡도

주어진 배열 nums를 한 번 탐색하고, 각 루프에서는 상수 연산을 수행하므로 O(n)의 시간복잡도를 가진다.

공간 복잡도

해시맵, 딕셔너리인 cnt를 사용해 중간 값을 저장하므로 주어진 nums의 사이즈와, 나머지 변수들을 저장하기 떄문에 공간복잡도는 O(n)이다.