(백준 알고리즘 문제풀이)2015번 수들의 합 4

문제

 

문제 링크

 

문제 접근

• N의 범위가 20만으로 매우크기 때문에 for문을 2번이상 돌리는 것은 효율적이지 않다고 생각했다. 
• 자료구조인 dictionary를 이용하는 것이 효율적이라고 생각한다.

코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
lst = list(map(int, sys.stdin.readline().split()))
memo = {0: 1}
sum_value = 0
result = 0

for val in lst:
    sum_value += val

    # 이전 누적값에서 - K인 것이 존재한다면 result에 추가해줌
    if sum_value - K in memo.keys():
        result += memo[sum_value-K]

    if sum_value not in memo.keys():
        memo[sum_value] = 1
    else:
        memo[sum_value] += 1

print(result)
# print(memo)

느낀점

기본적인 코딩 문제를 왜이렇게 복잡하게 생각하는지 모르겠다.