✏️

rangeMinimun

Question

정수를 요소로 갖는 배열과 특정 구간을 입력받아, 해당 구간 내에서 최소값을 리턴해야 합니다.

입력

인자 1 : arr

•

number 타입을 요소로 갖는 배열

•

arr.length는 500,000 이하

•

arr[i]는 -100,000 이상 100,000 이하의 정수

인자 2 : ranges

•

number 타입을 요소로 갖는 배열

•

ranges.length는 10,000 이하

•

ranges[i]는 특정 구간을 의미

•

ranges[i][0]은 i번째 구간의 시작 인덱스

•

ranges[i][1]은 i번째 구간의 마지막 인덱스

출력

•

배열(arr)를 리턴해야 합니다. (입출력 예시 참고)

•

arr[i]는 i번째 구간(ranges[i])의 최소값

Test Case 1

const arr = [1, 3, 2, 7, 9, 11];
const mins = rangeMinimum(arr, [
  [1, 4],
  [0, 3],
]);
console.log(mins); // --> [2, 1]
Shell
복사

Test Case 2

Shell
복사

Solve

const rangeMinimum = function (arr, ranges) {
  // ts: tree start. te: tree end
  // arr의 ts부터 te까지를 tree로 만든다.
  const createMinTree = (arr, ts, te) => {
    // base case
    if (ts === te) {
      return { value: arr[ts] };
    }

    // recursive case
    // 현재 범위를 절반을 기준으로 왼쪽과 오른쪽으로 나눈다
    const mid = parseInt((ts + te) / 2);
    const left = createMinTree(arr, ts, mid);
    const right = createMinTree(arr, mid + 1, te);

    return {
      value: Math.min(left.value, right.value),
      left,
      right,
    };
  };
  const tree = createMinTree(arr, 0, arr.length - 1);

  // rs: range start, re: reange end
  const findMin = (ts, te, rs, re, tree) => {
    // 현재 tree와 구간이 정확히 일치하거나
    // 구간이 tree를 포함할 경우
    if (rs <= ts && te <= re) {
      return tree.value;
    }

    // 현재 tree에 주어진 구간이 겹치지 않는 경우
    if (te < rs || re < ts) {
      return Number.MAX_SAFE_INTEGER;
    }

    // 겹치는 부분이 존재하는 경우
    const mid = parseInt((ts + te) / 2);
    return Math.min(
      findMin(ts, mid, rs, re, tree.left), //
      findMin(mid + 1, te, rs, re, tree.right)
    );
  };

  const mins = ranges.map((range) => {
    const [start, end] = range;
    return findMin(0, arr.length - 1, start, end, tree);
  });
  return mins;
};
JavaScript
복사

실행시간 : ms

class SegmentTree {
  constructor(target) {
    this.tree = [];
    this.target = target;
    this.init(0, 0, this.target.length - 1)
  }
  init(index, left, right) {
    if (left === right) {
      this.tree[index] = this.target[left];
      return this.target[left];
    }

    const mid = parseInt((left + right) / 2);
    const leftNode = this.init(index * 2 + 1, left, mid);
    const rightNode = this.init(index * 2 + 2, mid + 1, right);
    this.tree[index] = Math.min(leftNode, rightNode);

    return this.tree[index]
  }
  find(rangeStart, rangeEnd) {
    return this.getRangeMin(0, 0, this.target.length - 1, rangeStart, rangeEnd);
  }
  getRangeMin(index, left, right, rangeStart, rangeEnd) {
    if (left > rangeEnd || right < rangeStart) return 100000;

    if (left >= rangeStart && right <= rangeEnd) return this.tree[index];

    const mid = (left + right) >> 1;
    const leftNode = this.getRangeMin(index * 2 + 1, left, mid, rangeStart, rangeEnd)
    const rightNode = this.getRangeMin(index * 2 + 2, mid + 1, right, rangeStart, rangeEnd);

    return Math.min(leftNode, rightNode);
  }
}

const rangeMinimum = function (arr, ranges) {
  let sgt = new SegmentTree(arr);
  const result = [];
  for (let i = 0; i < ranges.length; i++) {
    let [start, end] = ranges[i];
    result.push(sgt.find(start, end))
  }
  console.log(sgt.tree)
  return result;
};
JavaScript
복사

실행시간 : ms