[HackerRank] Array Manipulation

Array Manipulation | HackerRank

---

  a-b 구간에 k를 더해나가면서 가장 큰 k 누적 값을 찾는 문제이다. 예제를 살펴보자.

 

1. 예제

예시

  문제에서는 query라는 이름으로 (a, b, k)의 순서쌍이 여러개 주어진다. 이 쿼리들을 0으로만 구성된 배열에 적용해나가면서 최종 배열의 최대 값을 찾는 문제이다. 단, 인덱스는 1부터 시작한다.

 

  처음에는 모든 값이 0이다.

  (1, 5, 3) 은 배열의 1번부터 5번까지 3을 더하라는 의미이다. 실행 결과는 step1 이다.

  (4, 8, 7) 은 배열의 4번부터 8번까지 7을 더하라는 의미이다. 실행 결과는 step2 이다.

  (6, 9, 1) 은 배열의 6번부터 9번까지 1을 더하라는 의미이다. 실행 결과는 step3 이다.

  최종 배열인 step3에서 가장 큰 값은 10이다. 따라서 정답은 10이다!

 

  이 문제를 직접 구현하는 것은 어렵지 않다. 0으로 초기화된 배열에 쿼리를 일일이 갱신해나가면 된다. 그러나 이러한 구현 방법은 문제에 주어진 시간을 초과하게 된다. 

 

2. 풀이

Ranges

  구간이 여러 개 존재하는 문제들(추석트래픽 문제, 단속카메라 문제)의 특징은 구간의 경계 부분에서 중복이 가장 많이 발생한다는 점이다. 이 문제도 마찬가지이다. 따라서 경계 부분의 값만 정확히 계산하여 그 중 가장 큰 값을 가져와도 문제의 답을 맞출 수 있다.

 

더 간단한 예제

  더 간단한 예제와 답을 살펴보자. 위 그림에서 step2는 최종 배열이다. 최종 배열에서도 각 쿼리의 범위에 따라 누적 합의 범위가 달라지는 것을 볼 수 있다.

 

  1-2 구간은 0부터 1번 쿼리의 시작 부분이다.

  3-4 구간은 1번 쿼리 시작부터 2번 쿼리 시작 부분이다.

  5-6 구간은 2번 쿼리 시작부터 1번 쿼리 끝 부분이다.

  7 구간은 1번 쿼리 끝부터 2번 쿼리 끝 부분이다. 

  8-10 구간은 2번 쿼리 끝부터 배열의 마지막 부분이다.

 

  각 구간의 특징이 보이는가? 각 구간의 값은 쿼리의 값만큼 증가하거나 감소된다. 쿼리의 시작 경계부터 시작했다면 해당 구간은 이전 구간의 값보다 k 만큼 증가하고, 쿼리의 끝 경계부터 시작했다면 해당 구간은 이전 구간의 값보다 k 만큼 감소하고 있다. 각 쿼리의 시작과 끝 부분에만 +k 혹은 -k를 하여 이러한 변화량의 누적 배열을 만든다면 처음 방법보다 데이터 업데이트가 덜 발생하면서도 최종적으로 발생되는 누적 값들을 구할 수 있지 않을까?

 

문제풀이과정

  위 내용을 바탕으로 각 쿼리가 발생할 때마다 시작 부분은 +k, 끝부분 +1에는 -k를 수행한 것이다. 

 

  query 1은 [1, 5, 3] 이므로 1번에 +3, 쿼리 범위가 끝난 직후인 6에 -3을 수행했다. 

  query 2는 [5, 8, 7] 이므로 5번에 +7, 쿼리 범위가 끝난 직후인 8에 -7을 수행했다.

  query 3은 [6, 9, 1] 이므로 6번에 +6, 쿼리 범위가 끝난 직후인 10에 -1을 수행했다.

 

  query의 변화량들을 누적한 최종 결과인 prefix sum 배열을 만들었다. 4에 해당하는 부분은 query 1의 변화량인 +3, query 2의 변화량인 +7 이 적용되어 10으로 최대 누적 값을 가진다는 것을 볼 수 있다.

 

3. 코드

function arrayManipulation(n, queries) {
  const arr = Array(n).fill(0);
  for (const query of queries) {
    const [a, b, k] = query;
    arr[a - 1] += k;
    arr[b] -= k
  }

  let max = 0;
  for (let i = 1; i < arr.length; i++) {
    const value = arr[i - 1] + arr[i];
    arr[i] = value;
    if (max < value) max = value;
  }
  return max;
}

---

참고: https://brokensandals.net/technical/programming-challenges/hackerrank-array-manipulation/