Contents

Array Manipulation

Array에서 특정 구간에 주어진 숫자를 더했을 때, 최종적으로 가장 큰 수를 찾는 문제이다.

Problem

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.

함수에 두 가지 input이 주어진다. n은 array의 길이 query는 배열로 각 행에 시작위치, 끝위치, 더해지는 숫자가 주어진다. Difficulty가 hard로 timeout이 빡빡해 최적화에 대한 고민을 해보아야 하는 문제이다.

Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def arrayManipulation(n, queries):
    heaviside = [0] * n
    for i, j, k in queries:
        heaviside[i-1] += k
        if j <= (n-1):
            heaviside[j] -= k
            
    max_val = 0
    cum_sum = 0
    for i in heaviside:
        cum_sum += i
        if cum_sum > max_val:
            max_val = cum_sum
    return max_val

Explanation

문제 자체를 푸는 것은 어렵지 않다. 하지만 time complexity를 떨어뜨리기 위해서 효율적인 방법을 고민해보아야 한다. 이 문제를 푸는데 사용한 핵심 아이디어는 Heaviside step function이다. Heaviside step function은 다음과 같은 함수이다.

$$H(x) \coloneqq {\begin{cases}1 ,& x > 0 \cr 0, & x < 0\end{cases}}$$

신호처리분야에서 자주 사용하는 함수인데 이를 활용하면 $x=1$부터 $x=3$까지 100을 더하는 것은 $100(H(x-1) - H(x-3))$로 나타낼 수 있다. 이 아이디어를 사용하면 array에 실제 값을 모두 넣을 필요 없이, 시작점과 끝점의 증감만 고려해주면 된다.

따라서 첫번째 반복에서는 시작점과 끝점에 Heaviside의 $y$값을 넣어준다. 끝부분에서 out of range가 되지 않도록 처리해주는 부분에 유의하자. 이렇게 하면 실제 더할 필요없이 heaviside array에는 수가 어떻게 증감하는지에 대한 정보만 담기게 된다. 이 array를 sweep하면서 가장 큰 수를 찾기만 하면된다.

Reference