[해커랭크] (Data Structures - Arrays) Array Manipulation (javascript)

배열의 구간 최대합 구하기
에러케이스 수정 중 누적값 알고리즘 prefixSum(구간합) 발견하여 참고함

조건

• n개의 배열(arr)은 인덱스가 1부터 시작
• 쿼리(queries)는 query를 인자를 가지는 배열로 
  • query= [a, b, k]  (이때, a,b는 index, k는 값)
• 주어진 두 개의 인덱스(a-b)사이에 값(k)를 추가
• 해당 배열의 최댓값을 반환

 

제한사항

• 3 ≤ n ≤ 10⁷
• 1 ≤ m ≤ 2 * 10⁵
• 1 ≤ a ≤ b ≤ n
• 0 ≤ k ≤ 10⁹

 

나의 풀이

• 단순 풀이만이 아니라 생소한 구간합 이라는 알고리즘을 처리해야 하기 때문에 샘플데이터를 기반으로 풀이
  • n = 5, m = 3, querie는 아래와 같음

a b  k
1 2 100
2 5 100
3 4 100

• 일반 로직대로 풀이하면 아래 표와 같음
  • queries의 배열값을 순차적으로 순회하며 주어진 구간내에 값(k)을 할당 (n x m 배열)
  • 순회가 끝났을 때, 각 열의 값을 합함(SUM) ( n x 1 배열)
  • SUM 배열중 최댓값 추출

a  b  k	n=1	n=2	n=3	n=4	n=5
1  2  100	100	100
2  5  100		100	100	100	100
3  4  100			100	100
SUM	100	200	200	200	100

•  해당 값을 구간합(prefixSum) 로직을 이용하면 한결 간결하게 처리할 수 있음
• 그 계산 결과는 아래 표와 같음
  • queries의 배열값을 순차적으로 순회하며 주어진 구간 a와 b+1에 값을 할당하기 위해 n+1 배열 생성 ((n+1) x m 배열)
    • a에는 주어진 값(k)을 할당하고, b+1 에는 -k를 할당
      • a~b 구간내에는 k 값이 존재하는 모양이기 때문에 b+1에 -k를 할당
  • 순회가 끝았을 때, 각 열의 값을 합함(SUM) ((n+1) x 1 배열)
  • SUM의 누계값을 구하면서(ACC), 최댓값을 추출

a  b  k	n=1	n=2	n=3	n=4	n=5	n=6
1  2  100	100		-100
2  5  100		100				-100
3  4  100			100		-100
SUM	100	100	0	0	-100	-100
ACC		100 + 100	200 + 0	200 + 0	200 + (-100)	100 + (-100)
	100	200	200	200	100	0

• 해당 풀이를 기반으로 함수를 작성하여 풀이함

 

• n개의 빈 배열 (arr) 생성
  •  구간합 알고리즘을 위해 n+1개 배열 생성
    • 누적값이 구간영역까지 유지되고 그 이후 제거되어야 하기 때문에 n+1 배열 생성
• queries를 순회하면서 arr[a-1] += k, arr[b] -= k 연산
  
  • 인덱스 1부터 시작하는 풀이를 0-인덱스로 처리
• reduce를 이용하여 합한 값을 누적하며 최댓값 비교

// 생략

/*
 * Complete the 'arrayManipulation' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. 2D_INTEGER_ARRAY queries
 */

function arrayManipulation(n, queries) {
  // Write your code here
  const arr = [...new Array(n+1)].fill(0);
  const len = queries.length;

  for (let i = 0; i < len; i++) {
    const [a, b, k] = queries[i];
    arr[a-1] += k;
    arr[b] -= k;
  }
  
  let max = 0;
  const reducer = arr.reduce((a, b) => {
    a += b;
    max = Math.max(max, a);
    
    return a;
  }, 0);

  return max;
}

// ..후략

결과