Array Manipulation Javascript로 풀기 + 해설

/*

n과 m이 주어진다.

n은 배열의 길이이며, m은 추가할 횟수이다.

배열 queries는 m/3개의 a,b,x를 가진다.

a부터 b까지 index에 x를 더한다.

 

위 작업을 수행한 뒤 가장 큰 값을 리턴하는 함수이다.

당장 무슨 아이디어가 떠오르지 않는다.

거친 방식을 이용해서 문제를 풀어본다.

예를들어 

 

var n = 10;

var queries = [[1,5,3],[4,8,7],[6,9,1]];

일때

 

초기값

0 0 0 0 0 0 0 0 0 0

 

1 5 3 ->

3 3 3 3 3 0 0 0 0 0

 

4 8 7 ->

3 3 3 10 10 7 7 0 0 0

 

6 9 1 ->

3 3 3 10 10 8 8 1 1 0

 

이런식으로 쿼리를 돌면서 배열에 다 넣어주는 것이다.

시간복잡도는 n^2

 

당연하지만 시간복잡도 때문에 안된다.

온갖 방법을 다 써봤지만 실패했다.

결국 구글링으로 해결

배열에 대한 관점을 바꾸어야만 해결할 수 있다.

 

예를들어 1 5 3 일때 의미는 다음과 같다.

 

1부터 5까지 3이다.

-> 1부터 5까지 +3이고 그 다음값부터는 -3이다.

1 5 3이 각각 x y z라면

 

x부터 y까지 +z 이고 그 다음 값 부터는 -z이다.

 

즉 

3 0 0 0 0 -3 0 0 0 0

이 된다.

 

맨 마지막 최대값을 구할때에는 0부터 n까지의 합을 각 부분합으로 구하면 된다.

 

arr[0] = arr[0]

arr[1] = arr[0]+arr[1];

arr[2] = arr[1]+arr[2]

...

이런식으로

 

그럼 위 문제는 최종적으로 아래의 배열을 갖는다.

[ 3, 0, 0, 7, 0, -2, 0, 0, -7, -1 ]

각 항목의 부분합을 구하면 최대값은 10이다.

 

또한 최대값을 구할때 Math.max 함수를 쓰면 시간초과가 되므로 쓰지말자.

 

진짜 천재적인 아이디어라고 생각함.

*/

 

var n = 10;

var queries = [[1,5,3],[4,8,7],[6,9,1]];

 

function arrayManipulation(n, queries) {

    var arr = [];

    for(var i=0;i<n;i++){

        arr.push(0);

    }

    for(var i=0;i<queries.length;i++){

        arr[queries[i][0]-1]+=queries[i][2]

        arr[queries[i][1]]-=queries[i][2]

    }

    console.log(arr)

    var max = Number.MIN_VALUE;

    for(var i=1;i<arr.length;i++){

        arr[i]=arr[i]+arr[i-1];

        if(max<arr[i]){

            max=arr[i];

        }

        

    }

    return max

}

arrayManipulation(n, queries);