문제

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

입력 값은 행렬의 크기$(m * n)$ 와 $queries$(연산을 의미, a, b, k)를 받는다. 여기서 쿼리의 의미는 a 는 시작 인덱스, b 는 종료 인덱스, k 는 더할 값이다.
행렬 안에 있는 각 쿼리는 배열의 a 인덱스부터 b 인덱스까지 k 값을 더해가며 더한다.그리고 모든 쿼리는 수행하고 난 뒤, 배열의 요소 중 가장 큰 값을 반환하면 된다.

예시

---

입력값

5 3
1 2 100
2 5 100
3 4 100

출력값

200

설명

1. After the first update the list is 100 100 0 0 0.
2. After the second update list is 100 200 100 100 100.
3. After the third update list is 100 200 200 200 100.

The maximum value is $200$

풀이

1. Brute Force로 풀이(시간초과)

def arrayManipulation(n, queries):
    # Write your code here
    # k값을 더할 배열 생성
    sum_list = [0] * (n + 1)

    # 배열안에있는 쿼리를 돌면서 k값을 더한다.
    for i in queries:
        for j in range(i[0], i[1] + 1):
            sum_list[j] += i[2]
            
    # 최대값 반환
    return max(sum_list)

• 배열안에있는 쿼리를 모두 돌면서 k값을 각 구간별로 더하여 최대값을 구한 풀이이다.

• Brute Force로 풀이하여 시간복잡도 $O(m * n) => O(n^2)$ 로 시간초과가 났다.

2. Prefix Sum(구간합)을 이용한 풀이

def arrayManipulation(n, queries):
    # Write your code here
    # 부분합 리스트
    k_list = [0] * (n + 1)

    # 리턴할 가장 높은 값
    max_val = 0

    # 부분합 리스트 업데이트
    for s, e, k in queries:
        k_list[s] += k
        if e + 1 <= n:
            k_list[e +1] -= k
    
    # max_val과 비교하기 위한 변수 설정
    val = k_list[0]

    # 부분합의 누적합을 구하면서 최대 값을 구한다.
    for i in range(1, n+1):
        val += k_list[i]
        if val > max_val:
            max_val = val
            
    return max_val

• 구간합을 이용하여 모든 구간의 합을 구하는 것이 아니라 시작 인덱스와 종료인덱스에 해당 구간의 값을 저장하고, 그 저장한 값을 누적값 리스트로 만들어 최대값을 구한 풀이이다.

• prefix sum 개념

• Prefix Sum을 이용하여 시간복잡도 $O(n^2) => O(n)$ 으로 한층 더 성능이 좋아졌다.

이문제는 보기에는 쉬워보였으나, 막상 풀어보면 시간초과가 되어 시간복잡도를 줄여서 풀이하는 것이 어려웠엇다. 또 구간합의 개념을 이해하는 것도 쉽지만은 않았다.