SWEA - 구간합 [Python]

 문제

 

https://swexpertacademy.com/main

SW Expert Academy

 

 문제 상황

 

- N개의 정수가 들어있는 배열에서 연속된 M개 숫자의 합이 가장 클 때와 가장 작을 때를 계산하여 그 차이를 출력한다.

 

 해결 전략

 

- 배열을 입력 받아 탐색하면서 선형적으로 최대값과 최소값을 계산하면 O(N)에 가능하다.

 

 코드

 

# 새로운 코드
# sum 연산을 for문 밖에서 해줌으로써 O(N^2)가 아니라 O(2N) 즉, O(N)으로 연산
# 하나씩 추가되므로 앞에 것을 하나 빼주고 뒤에 새로운 것만 더해 총 M개 유지
 
t = int(input())
for time in range(t):
    N, M = map(int, input().split())
    N_list = list(map(int, input().split()))
    total = sum(N_list[:M])
    mx, mn = total, total
    for i in range(M, N):
        total += N_list[i] - N_list[i-M]
        if total > mx :
            mx = total
        if total < mn :
            mn = total
    print(f"#{time + 1} {mx-mn}")
 
# 예전 코드
# for문 안에 sum 이라는 O(N) 함수를 사용하여 O(N^2) 의 느린 속도로 연산된다.
 
# for i in range(t):
#     n, m = map(int, input().split())
#     maxnum = 0
#     minnum = 1000000
#     nlist = list(map(int, input().split()))
#     for j in range(n-m+1):
#         total = sum(nlist[j:j+m])
#         if total > maxnum :
#             maxnum = total
#         if total < minnum :
#             minnum = total
#     print("#{} {}".format(i, maxnum-minnum))

 

 

 해설

 

- Sum 연산을 for문 안에서 계속 해주는 것이 아니라 처음 한번만 해서 새로운 값이 갱신될 때마다 기존 합의 처음 값을 빼주고 새로운 값을 더해줌으로써 총 길이 M을 유지하고 동시에 연산 속도는 O(N)으로 낮춰주었다.

 

 새로 학습한 것 & 실수 

 

- 부분합 연산은 값이 갱신될때마다 할 필요가 없이 변하는 값만 조정해줘도 충분하다.

 

 

출처 - https://swexpertacademy.com/main