[ 파이썬(python) ] 이것이 코딩 테스트다 - 구간 합 계산(Prefix_sum)

📍 백준 11659 - 구간 합 구하기 4

백준 11659 - 구간 합 구하기4

---

⚡️ 나의 풀이

이 문제를 그냥 구현한다면 시간 초과에서 벗어나지 못할 것이다. 바로 시간 복잡도가 높기 때문인데, 이럴 때 시간 복잡도를 낮출 적절한 알고리즘이 바로 prefix_sum이다. prefix_sum의 난이도는 어렵지 않다.

 

서두에서 말했듯이 이 문제를 prefix_sum을 사용하지 않고 구현할 때 N, M의 입력 범위가 100,000이 넘어간다면 시간 복잡도는 O(NM)이 되므로 1초 내에 구현할 수가 없다. 알고리즘을 설계할 때마다 고려해야 하는 점은 여러 번 사용될 만한 정보는 미리 구해서 저장해 놓을수록 유리하다.

 

구현 방법은 간단한데, 각각의 합들을 새로운 배열에 저장해뒀다가 나중에 입력에 구간이 들어오면 해당 구간을 index로 바꿔서 출력해주면 된다. 이때, index를 헷갈리게 하지 않기 위해 새로운 배열에 0을 추가해둔다. 매 입력이 들어올 때 P[right] - P[left-1]을 수행하면 계산시간은 O(1)이 되고, 결과적으로 N개의 데이터와 M개의 입력이 있을 때, 전체 구간 합을 구하는 작업은 O(N+M)의 시간이 보장된다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))
prefix_sum = [0]    # init prefix_sum    

temp = 0    
for i in arr:    # accumulate arr section 
    temp += i
    prefix_sum.append(temp)

for i in range(m):
    a, b = map(int, input().split())
    print(prefix_sum[b] - prefix_sum[a-1])