PrefixSum_Leetcode_523. Continuous Subarray Sum [swift]

https://leetcode.com/problems/continuous-subarray-sum/description/

 

반성

아무리 생각해봐도, length >= 2조건을 만족하려면 부분합을 이루는 element를 기록하는 수 밖에 생각나지 않았다.

그런데 그러면 PrefixSum을 쓸 이유가 없으니,,, 방법이 떠오르지 않는 것이었다.

그래서 GPT에 질문했는데, 결국 이 내용이 중요한 열쇠였다.

시간을 들여서 고민했는데 모르면 정답에 접근하기 어렵다는 얘길 들었다.

이후로, 꽤 고민하고 안나오면 질문하게 되었는데, 더 고민 할 수는 없었을까,,,

 

정답 코드

이 코드는 성능이 정말 안좋다. 하위 5%다.

왜냐하면, 본래 반환은 하나라도 존재하면 true를 반환하여 종료가 빠를 수 있는데 전부 확인하기 때문.

코드 한줄 추가하면 성능이 훨씬 좋아진다.

하지만 연습을 위해서 같은 방식을 고수한다.

class Solution {
    func checkSubarraySum(_ nums: [Int], _ k: Int) -> Bool {
        var sol = 0
        var map = [Int: [Int]]()
        map[0] = [-1]

        func recursive(_ curSum: Int, _ curIdx: Int) {
            guard curIdx < nums.count else { return }
            let newSum = curSum + nums[curIdx]
            let remainder = newSum % k
            if let values = map[remainder] {
                for i in values {
                    if abs(i - curIdx) >= 2 { sol += 1}
                }
            }
            map[remainder, default: []].append(curIdx)
            recursive(newSum, curIdx + 1)
            map[remainder]!.removeLast()
        }

        recursive(0,0)

        return sol > 0
    }
}