[파이썬] 4835. 구간합

swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


N개의 정수가 들어있는 배열에서 이웃한 M개의 합을 계산하는 것은 디지털 필터링의 기초연산이다.

M개의 합이 가장 큰 경우와 가장 작은 경우의 차이를 출력하는 프로그램을 작성하시오.
 

다음은 N=5, M=3이고 5개의 숫자 1 2 3 4 5가 배열 v에 들어있는 경우이다.
 

v

1

2

3

4

5

 

v

1

2

3

4

5

이웃한 M개의 합이 가장 작은 경우 1 + 2 + 3 = 6
 

v

1

2

3

4

5

이웃한 M개의 합이 가장 큰 경우 3 + 4 + 5 = 12
 

답은 12와 6의 차인 6을 출력한다.

 

[입력]
 

첫 줄에 테스트 케이스 개수 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	#1 21 #2 11088 #3 1090

 

Memory error occured, (e.g. segmentation error, memory limit Exceed, stack overflow,... etc)가 초반에 자주 떴던 이유는 input()을 2번하면 변수가 2개 있어야하는데 1번 써놓고 잘 나오나 출력돌렸기 때문이다.

 

🎨 나의 풀이

 

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, M = map(int, input().split())		# 정수의 개수 N과 구간의 개수 M 
    ai=list(map(int, input().split()))		# N개의 정수
    length=len(ai)
    i=0
    ans=list()						# 이웃한 M개의 합을 계산한 결과들을 담은 리스트
      
    while True:
        if i > length-M:		# M개씩 합을 만들어야하므로
            break
        ans.append(sum(ai[i : i+M]))
        i+=1
        
    print('#%d %d' %(test_case, max(ans)-min(ans)))
    

 

인덱스 0부터 length-M까지 이웃한 M개의 합을 각각 구해서 리스트 ans에 담는다.

ans에서 가장 큰 값과 가장 작은 값의 차이를 구해서 출력한다.

 

🎀 다른사람 풀이

 

TC = int(input())

for tc in range(1, TC+1):
    N, M = map(int, input().split())
    Data = list(map(int, input().split()))

    lst = []
    for i in range(N-M+1):
        lst.append(sum(Data[i:i+M]))

    print('#%s %d'%(tc, max(lst)-min(lst)))

 

나랑 같은 알고리즘.

아 ai의 길이를 구할 필요가 없었다. N을 쓰면 되는데