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
|
|
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하면서 가장 큰 수를 찾기만 하면된다.