[누적합/백준] 2015번 : 수들의 합 4

- 문제 : https://www.acmicpc.net/problem/2015

 

문제 이해

- 주어진 배열에서 연속된 부분 배열의 합이 K가 되는 배열의 개수를 구한다. 

- 각 인덱스까지의 누적합을 기준으로 fast_sum[b] - fast_sum[a] == k 가 되는 경우를 찾으면 된다.

 

풀이 로직

1. 각 인덱스까지의 누적합을 fast_sum에 추가한다. 

fast_sum = [0] * n
fast_sum[0] = arr[0]
for i in range(1, n):
    fast_sum[i] += arr[i] + fast_sum[i - 1]

 

2. fast_sum[i] + target == k를 만족하는 target을 가지는 fast_sum의 원소 개수를 센다. 

2-1. 0 ~ (i - 1)에서의 원소를 반복문을 돌면서 target 값을 가지는 원소를 셀 수 있지만, 이렇게 하면 시간이 오래 걸린다. 

2-2. 그래서 인덱스 i까지 진행하면서 나왔던 누적합을 가지고 있는 딕셔너리 count를 이용한다. count는 {누적합 : 개수}의 형태.

2-3. target == 0이라면 arr[i]가 k라는 의미이므로 answer += 1를 해준다. 

2-4. target이 count에 key값으로 있다면 count[target] 값을 answer에 더해준다. (count[target]의 값만큼 인덱스 i와 부분합이 k인 인덱스 개수를 의미함)

 

3. fast_sum[i] 값이 count에 key 값으로 없다면 지금까지 없던 누적합 값이므로 count에 {fast_sum[i] : 0}으로 추가한다. 

3-1. 인덱스 0부터 i 까지의 누적합의 개수를 +1 한다. (count[fast_sum[i] += 1)

 

4. 위에서 구한 answer를 출력한다. 

 

배운 것 

반복문으로 했을 때 시간이 오래 걸리면 해시(딕셔너리)를 이용하는 것을 배웠다. 

 

정답 풀이 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
arr = list(map(int, input().split()))

fast_sum = [0] * n
fast_sum[0] = arr[0]
for i in range(1, n):
    fast_sum[i] += arr[i] + fast_sum[i - 1]

count = {} # 내 앞에 target 값이 몇 개 있는지 확인하는 딕셔너리    
answer = 0
for i in range(n):
    target = fast_sum[i] - k
    
    if target == 0 :
        answer += 1    
    if target in count : 
        answer += count[target]
  
    if fast_sum[i] not in count:
        count[fast_sum[i]] = 0
   
    count[fast_sum[i]] += 1  # fast_sum[i]인 수가 하나 더 들었으니까
            
print(answer)