4835. [파이썬 S/W 문제해결 기본] 1일차 - 구간합

문제 출처

4835. 1일차 - 구간합

---

• 문제 해석

  • N개 요소가 있는 배열에서 이웃한 M개 요소의 합이 최대일때와 최소일때의 차이 출력

• 입력

  • 배열 크기 N, 구간 크기 M
  • 배열 Arr

• 출력

  • 구간 합 차이

• 아이디어

  • N-M +1번만큼 for문을 돌자!
  • 돌면서 구간합을 구해서 리스트에 저장
  • 리스트에서 max값과 min값을 빼서 출력

• 필요 변수

  • 구간합 저장할 빈 리스트 tmpSum

• 내 코드

# 입력받기
for tc in range(1, int(input())+1):
    N, M = map(int, input().split())
    Arr = list(map(int, input().split()))

    tmpSum = []

    # 배열 순회
    for i in range(N-M+1):
        tmpSum.append(sum(Arr[i:i+M]))

    print(f'#{tc} {max(tmpSum) - min(tmpSum)}')

• 피드백
  "코드가 간결하고 이해하기 좋은데요. 배열 크기가 작을 때는 상관이 없는데 배열 크기가 커질 수록 계속 구간마다 새롭게 값을 더해줘야해서 시간이 오래 걸릴 수 있는 구조입니다."
  → 내 코드는 1,2,3 / 2,3,4 / 3,4,5 / .... 이런 식으로 계한하기 때문에 구간합 구할 때 중복되는 요소가 존재한다.. 1,2,3 구한 후 1 날리고, 4만 추가한다면 시간 절약 가능하다는 의미!

• 피드백 코드

for tc in range(1, int(input())+1):
    N, M = map(int, input().split())
    Arr = list(map(int, input().split()))
 
    # 배열 순회
    s, e = 0, M-1
    min_sum = sum(Arr[:M+1])
    max_sum = min_sum
    cur_sum = min_sum
    s += 1
    e += 1
    while e < N :
        cur_sum = cur_sum - Arr[s-1] + Arr[e] 
        max_sum = max(cur_sum, max_sum)
        min_sum = min(cur_sum, min_sum)
        s += 1
        e += 1
 
    print(f'#{tc} {max_sum - min_sum}')