Array Manipulation

def arrayManipulation(n, queries):
    newArr = [0] * n

    for start, end, value in queries:
        newArr[start-1] += value
        if end < n:
            newArr[end] -= value

    total = 0
    maxVal = 0
    for v in newArr:
        total += v
        maxVal = max(maxVal, total)
    
    return maxVal

 

문제를 보는 순간 아이디어나 패턴이 떠오르면 바로 해당 방식으로 접근하지만, 대부분의 경우에는 그렇지 않기 때문에 거친 방식 으로 접근한다.

거친 방식이란?

시간 복잡도를 생각하지 않고 문제를 푸는 방식이다. Time out 을 신경쓰지 않는 해결 방안

 

그래서, 쿼리 만큼 반복문을 돌면서 시작점, 끝점 으로 반복문을 또 도는 이중 포문으로 설계 했다. 당연히 Time out!

 

흐음 어떻게 최적화를 할까? 시작점, 끝점 을 반복 안하고 최대값 을 얻어내는 방법은 무엇이 있을까?

유레카! 시작점과 끝점만으로 구해야한다. 두 수의 사이값들은 중요치 않다.

예를 들면

5 3
1 2 100
2 5 100
3 4 100

위의 쿼리가 주어졌을 때 기본 배열은 [0,0,0,0,0]이 된다.
먼저 1 2 100을 대입하면, [100, 0, -100, 0, 0]이 된다.
어떻게?

시작점에는 우선 값을 넣어준다. +100
끝점에는 다음 인덱스에 값을 빼준다. -100

왜 그럴까? 그건 바로 최대값을 구하는 방식 때문이다. 
나의 로직에서 최대값은 배열의 끝까지 순회 했을 때 누적합이 제일 큰 것이기 때문이다.

[100, 0, -100, 0, 0] - 1번째 쿼리
[100, 100, -100, 0, 0] - 2번째 쿼리
[100, 100, 0, 0, -100] - 3번째 쿼리

1번째 쿼리를 수행했을 때 배열의 결과다. 자세히 살펴보자.
1-2 인덱스에 100을 더해준다. 배열을 순회하면서 누적합을 시킨다. 
1번째는 100, 2번째는 100+0, 세번째는 100-100, 네번째는 0+0, 다섯번째는 0+0이다.

결과를 보면 우리가 원하는 모습이지 않은가? 1-2 인덱스에 100이 있다는걸 확인이 가능하다!

그래서 3번째 쿼리까지 최종 실행된 배열의 모습을 해석하면
1번째는 100, 2번째는 100+100, 3번째는 200+0, 4번째는 200+0, 5번째는 200-100

그래서 최대값은 200이 나온다.

 

위의 알고리즘은 기억해두면 유용하게 사용이 가능할 것 같다.