[백준] 2015번 수들의 합 4 ★★

💡문제접근

• 투 포인터를 이용한 방법도 아니었고 이걸 어떻게 풀어야 하는지 정말 오랫동안 고민했는데 쉽사리 해결방법이 떠오르지 않았다. 질문게시판에 있는 힌트를 참고했다.
• 각 누적합에 대한 개수를 저장하고 현재 수가 M일 때, -M의 개수를 세면 된다는 방법을 알려준 글을 보고 딕셔너리를 이용해야겠다고 생각했다.

💡코드(메모리 : 45708KB, 시간 : 152ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
nums = list(map(int, input().strip().split()))
prefix_sum = {0 : 1}

tot = 0
ans = 0
for i in nums:
    tot += i
    # tot : 누적 합
    # prefix_sum : 각 부분의 누적 합을 저장
    # tot - prefix_sum.key = M → tot - M이 prefix_sum에 있는지를 확인
    if tot - M in prefix_sum.keys():
        ans += prefix_sum[tot - M]
    if tot in prefix_sum:
        prefix_sum[tot] += 1
    else:
        prefix_sum[tot] = 1
print(ans)

💡소요시간 : 2d