[백준1275_자바스크립트(javascript)] - 커피숍2

🔴 문제

커피숍2

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const [n, q] = inputs[0];
const tree = Array(4 * n).fill(0);
const numbers = inputs[1];

const init = (start, end, node) => {
  if (start === end) return (tree[node] = numbers[start]);

  const mid = Math.floor((start + end) / 2);

  return (tree[node] = init(start, mid, 2 * node) + init(mid + 1, end, 2 * node + 1));
};

const update = (start, end, node, idx, diff) => {
  if (idx < start || end < idx) return;
  tree[node] += diff;

  if (start === end) return;
  const mid = Math.floor((start + end) / 2);

  update(start, mid, 2 * node, idx, diff);
  update(mid + 1, end, 2 * node + 1, idx, diff);
};

const sum = (start, end, node, left, right) => {
  if (start > right || end < left) return 0;
  if (left <= start && end <= right) return tree[node];

  const mid = Math.floor((start + end) / 2);

  return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
};

init(0, n - 1, 1);

for (let i = 2; i < inputs.length; i++) {
  const [x, y, a, b] = inputs[i];

  const s = Math.min(x - 1, y - 1);
  const e = Math.max(x - 1, y - 1);
  console.log(sum(0, n - 1, 1, s, e));

  const diff = b - numbers[a - 1];
  numbers[a - 1] = b;
  update(0, n - 1, 1, a - 1, diff);
}

🟢 풀이

⏰ 소요한 시간 : -

n개의 정수의 구간 합을 구해야 하고 수 변경이 빈번하게 발생하기 때문에 세그먼트 트리 유형이다.
세그먼트 트리를 만들기위해 4n의 크기를 가진 트리배열을 만들어주고, 초기 숫자들을 numbers에 할당해준다.

초기 숫자가 주어지기 때문에 init 함수를 통해 트리의 초기값을 세팅해준다.
init 함수는 구간 범위 start, end과 이 구간의 구간합을 저장할 인덱스인 node를 매개변수로 받는다.
start와 end가 같다면 그 값을 트리에 저장하고, 다르다면 중간값을 구해 재귀 호출하면서 트리를 채워준다.

이제 쿼리를 수행할텐데 y가 x보다 더 클 수 있으므로, 시작값과 끝 값 s, e를 명확히 정한 뒤 sum 함수를 호출해 구간합을 출력하면 된다.
sum 함수도 init 함수와 동일하게 start, end, node를 매개변수로 받고, 실제로 쿼리에서 구간합을 구하고자 하는 범위인 left와 right도 매개변수로 받는다.
그 후 left와 right가 구간을 벗어났다면 0을 리턴, 구간에 완전히 포함됐다면 구간합을 저장한 노드 tree[node]를 리턴한다.
구간에 완전히 포함되지 않았다면 중간값을 구해 재귀호출하며 구간합을 구한다.

마지막으로 업데이트 쿼리를 수행한다. a번째 요소를 b로 바꿔야 하기 때문에 b에서 a번째 요소를 빼 차이값 diff를 구한다. 그 후 초기 숫자값에도 변경사항을 반영한다.
트리를 업데이트 하기 위해 update함수를 수행한다.
update함수도 start, end, node를 매개변수로 받고, 추가로 쿼리에서 변경하기 위해 주어진 인덱스와 아까 구한 차이값 diff를 같이 받아준다.

변경할 idx의 범위가 start와 end 사이에 있지 않으면 종료하고, 범위 내에 있다면 diff를 반영한뒤 중간값을 구해 재귀호출하면 된다.

🔵 Ref