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

https://www.acmicpc.net/problem/2015

공부 날짜 : 2023.01.29
정답 참조 여부 : O

1차원 누적 합 중에서 특정수의 개수를 구하는 문제이다.

---

문제를 보자마자 전혀 감이 안온 문제였다.

특정구간의 합을 빠르게 구하기 위한 방법이 누적합인데 모든 구간을 탐색하는 거면 그냥 일반합으로 구하는거나 시간 복잡도는 같다고 느꼈기 때문이다.

그렇기 때문에 시도조차 못해보고 정답을 참조 했는데, 정말 신박한 방법(?)이였다.

순차적으로 누적합을 구하면서 k가 되기위해 빼야하는 수가 이전에 구한 누적합이 있는지 체크를 해서 정답을 구했다.

딕셔너리를 많이 써보지 않아서 정답을 본 뒤에 리스트로 구현해서 인덱스 접근 방식으로 할려했지만 리스트로 구현하면 크기가 20억이나 되어야하기에 어쩔수 없이 정답을 참조한대로 딕셔너리로 만들었다.

개인적으로 in을 안좋아 한다. 리스트에서 in을 사용하는건 모든 요소를 다 세봐야 하는거기 때문에 연산이 많이 필요하다고 알아서 별로 안좋아 하는데 in을 사용하지 않은 로직이 떠오르지 않아, 거의 그대로 코드를 작성했고,

 if sum_val in sum_dict.keys():
        sum_dict[sum_val] += 1
    else:
        sum_dict[sum_val] = 1

이 부분만

sum_dict[sum_] = sum_dict.get(sum_ , 0) + 1

이런식으로 수정해 줬다.

이번 문제는 진짜 감도 안온 문제였다. 사실 몇날 며칠 동안 고민했다면 어쩔까 싶긴 했지만, 아마 딕셔너리를 별로 좋아하지 않는 나로선, 이전의 누적합을 기록할 방법을 생각하지 못해서 아마 안했을거 같다.

누적합 알고리즘을 활용하는 새로운 유형을 익힐 수 있었던 좋은 문제였다.

소스코드

import sys
input = sys.stdin.readline
###############################################

n, k = map(int, input().split())
input_data = list(map(int, input().split()))  # 배열 데이터

# 누적 합 딕셔너리
# list의 index로 접근하려고 하면 index길이가 최대 20억이 되어야됨
sum_dict = {0: 1}

sum_ = 0
answer = 0

for i in input_data:
    sum_ += i

    # 현재까지 누적합 중에서 누적합 - (이전 누적합) = k 가 있으면
    # 즉 누적합 - k값이 이전에 나왔으면 정답개수 추가
    if sum_ - k in sum_dict.keys():
        answer += sum_dict[sum_ - k]

    # 누적 합 딕셔너리 갱신
    sum_dict[sum_] = sum_dict.get(sum_, 0) + 1

print(answer)