4835. 파이썬 S/W 문제해결(알고리즘) | 구간합

문제 4835

[입력] 
첫 줄에 테스트 케이스 개수 T가 주어진다.  ( 1 ≤ T ≤ 50 )
다음 줄부터 테스트케이스의 첫 줄에 정수의 개수 N과 구간의 개수 M 주어진다. ( 10 ≤ N ≤ 100,  2 ≤ M ＜ N )
다음 줄에 N개의 정수 ai가 주어진다. ( 1 ≤ a ≤ 10000 )
 
[출력] 
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

출처 SWEA

문제에 대한 모든 권리는 SW Expert Academy에게 있습니다.

 

 

2월 10일에 풀었을 때에는 구간합을 컨테이너(리스트)에 담아서 다시 for문을 돌려 최댓값과 최솟값을 구하는 방식으로 문제를 해결했다.

오늘 수업을 통해 최댓값이나 최솟값을 구해야하는 대상이 주어지지 않은 상황이라면!

즉, 이 문제처럼 계산을 통해 새롭게 구한 값 중에서 최댓값이나 최솟값을 구해야 하는 상황에서는 구한 값을 모두 리스트에 담아서 다시 계산할 것이 아니라 구한 값을 매번 비교하며 조건에 일치할 때 변수에 담아주면 된다는 꿀~~팁을 얻었다.

그래서 새롭게 코드를 짜보았다.

 

우선 처음 내가 풀었던 방식이다.

 

1) sort를 사용할 경우

T = int(input())

for tc in range(1, T+1):
    N, M = map(int, input().split())
    # 원본 숫자는 리스트에 담아두자
    nums = list(map(int, input().split()))
    # 숫자를 더할 변수와 더한 숫자를 담아둘 리스트
    total = 0
    totals = []
    # nums를 순회하면서 => 슬라이싱을 사용하면 for문 1개만 써도 됨
    for i in range(0, N-M+1):
        # M씩 묶어서 더하고
        for idx in range(i, i+M):
            total += nums[idx]
        # 묶어서 더한 숫자는 리스트에 추가하고
        totals.append(total)
        # 새로운 묶음으로 더해야 하므로 total은 다시 0으로 초기화
        total = 0
    # 더한 값이 담긴 리스트를 정렬하자
    sorted_totals = sorted(totals)
    print(f'#{tc} {sorted_totals[-1] - sorted_totals[0]}')

 

2) sort를 쓰지 않고 반복문을 통해 구하기

T = int(input())

for tc in range(1, T+1):
    N, M = map(int, input().split())
    # 원본 숫자는 리스트에 담아두자
    nums = list(map(int, input().split()))
    # 숫자를 더할 변수와 더한 숫자를 담아둘 리스트
    total = 0
    totals = []
    # nums를 순회하면서 => 슬라이싱을 사용하면 for문 1개만 써도 됨
    for i in range(0, N-M+1):
        # M씩 묶어서 더하고
        for idx in range(i, i+M):
            total += nums[idx]
        # 묶어서 더한 숫자는 리스트에 추가하고
        totals.append(total)
        # 새로운 묶음으로 더해야 하므로 total은 다시 0으로 초기화
        total = 0
    # sort를 쓰지 않고 더한 값이 담긴 리스트를 정렬하자
    length = len(totals)
    for j in range(length-1, 0, -1):
        for k in range(0, j):
            if totals[k] > totals[k+1]:
                totals[k], totals[k+1] = totals[k+1], totals[k]
    print(f'#{tc} {totals[-1] - totals[0]}')

 

---

sort도 추가적인 반복문도 필요 없는 ! 오늘 푼 방식

 

T = int(input())

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

    # 주어진 리스트를 돌면서 M개씩 더하자
    # 최종적으로 출력할 최댓값을 담을 변수와 최솟값을 담을 변수
    step_max = 1 # 문제에서 주어진 조건을 활용하자
    step_min = 10000 * M # 주어질 최대값은 10000이므로 이를 M개씩 더하면 최대값음 10000*M
    
    for i in range(N-M+1): # 인덱스 범위를 벗어나지 않도록 range를 설정한다
        step_sum = 0       # 구간합을 더해줄 변수
        for j in range(i, i+M): # i, i+1, i+2, ..., i+(m-1) 까지 더하도록 반복
            step_sum += arr[j]
            
        if step_max < step_sum: # 최댓값 구하기
            step_max = step_sum
        if step_min > step_sum: # 최솟값 구하기
            step_min = step_sum

    print(f'#{tc} {step_max - step_min}')