구간합 Python(SW Expert Academy)

난이도 : D2

문제번호 : 4835

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVFCzaqeUDFAWg#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

N개의 정수가 들어있는 배열에서 이웃한 M개의 합을 계산하는 것은 디지털 필터링의 기초연산이다. M개의 합이 가장 큰 경우와 가장 작은 경우의 차이를 출력하는 프로그램을 작성하시오

 

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  ( 1 ≤ T ≤ 50 ) 다음 줄부터 테스트케이스의 첫 줄에 정수의 개수 N과 구간의 개수 M 주어진다. ( 10 ≤ N ≤ 100,  2 ≤ M ＜ N ) 다음 줄에 N개의 정수 ai가 주어진다. ( 1 ≤ a ≤ 10000 )

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 10 3 1 2 3 4 5 6 7 8 9 10 10 5 6262 6004 1801 7660 7919 1280 525 9798 5134 1821 20 19 3266 9419 3087 9001 9321 1341 7379 6236 5795 8910 2990 2152 2249 4059 1394	#1 21 #2 11088 #3 1090

2. 문제풀이

---

파이썬 Intermediate 1일차 문제입니다. 구간합 문제입니다. 그냥 간단하게 2중반복문으로 계산해서 옆으로 이동하는 방법이 있습니다. 그렇지만 좀더 빠르게 구하는 방법이 있더라구요.   누적합을 이용해서 푸는 방법입니다. 입력배열을 받은뒤에 값을 누적한 배열을 하나 더 만듭니다. ex) 계산을 쉽게하기 위해 0번위치에는 0으로 넣고 시작한다. 입력배열의 0번째 값은 누적배열 1번째에 들어간다. 1번 인덱스자리는 0+1번 인덱스값, 2번 덱스자리는 누적된 1번 인덱스값 + 2번인덱스값 ..... n번은 누적된 n-1 + n   예제는 3칸을 구하는것으로 되어있으므로 위의 예시를 통해 보도록 하겠습니다. 3번째 자리의 누적합을 구하고 싶다면 누적합[3] - 누적합[3-3]을 계산하면 나옵니다. 5번째 자리의 누적합을 구하고 싶다면 누적합[5] - 누적합[5-3]을 계산하면 나옵니다. 이런 방식으로 문제를 풀게된다면 배열받는데 N 누적합구하는데 N 원하는값 계산하는데 N 합쳐서 3N으로 O(N)의 시간복잡도로 계산할 수 있습니다.   누적합을 구하지 않는다면 배열받는데N 2차원 반복문을 돌려 계산하는데 N^2 이므로 O(N^2)의 시간복잡도가 되므로 누적합의 방식이 속도가 더 빠르다고 볼 수 있습니다.

 

---

3. 소스코드

#구간합
length = int(input())
for l in range(1, length+1):
    N, M = list(map(int, input().split()))
    numbers = list(map(int, input().split()))
    #누적합을 구하기
    sumnumbers = [0] * (N+1)
    for i in range(1, N+1):
        sumnumbers[i] = numbers[i-1] + sumnumbers[i-1]
    #M번째를 최댓값과 최솟값으로 설정
    minnum = maxnum = sumnumbers[M]
    #반복을 돌면서 최솟값과 최댓값 찾기
    for i in range(M, N+1):
        minnum = min(minnum, sumnumbers[i] - sumnumbers[i-M])
        maxnum = max(maxnum, sumnumbers[i] - sumnumbers[i-M])
    #결과출력
    print("#{} {}".format(l, maxnum - minnum))