Portfolio

1️⃣ 문제

2️⃣ 문제 해결 전략

탐색 범위를 빠르게 찾기 위해 정렬 + 이진 탐색을 사용해야 합니다.

arr(납부 세금 내역)을 정렬해 둡니다. • 각 쿼리 X, Y마다, • 세금이 X 이상인 첫 인덱스 (lowerBound)와 Y 이하인 마지막 인덱스 (upperBound)를 이진 탐색으로 찾습니다. • 구간 내 사람 수는 upperBound - lowerBound입니다. (upperBound는 Y 초과인 첫 인덱스임에 주의)

3️⃣ 코드 및 설명

내 코드

완전탐색 ⇒ 시간초과


function solution(N, K, arr, queries) {
    var answer = Array.from({length: K},()=>0);
    for (let i=0;i<K;i++) {
        var [min,max] = queries[i]
        for (let j=0;j<N;j++) {
            if (arr[j]>=min && arr[j]<=max) {
                answer[i]++
            }
        }
    }
    return answer;
}

투포인트+누적합 ⇒ 메모리 초과


function solution(N, K, arr, queries) {
  var answer = [];
  arr.sort((a, b) => a - b);

  for (let i = 0; i < K; i++) {
    var [left, right] = [0, N - 1];
    var [min, max] = queries[i];
    while (left <= right && arr[left] < min) {
      left++;
    }
    while (left <= right && arr[right] > max) {
      right--;
    }
    answer[i] = right - left + 1;
  }

  return answer;
}

배열+누적합 ⇒ 메모리 초과


function solution(N, K, arr, queries) {
  var answer = [];
  var maxVal = Math.max(...arr);

  var newArr = Array.from({ length: maxVal + 1 }, () => 0);
  for (let a of arr) {
    newArr[a] += 1;
  }
  for (let i = 0; i < K; i++) {
    var [min, max] = queries[i];
    if (max > maxVal) {
      max = maxVal;
    }

    var sum = newArr.slice(min, max + 1).reduce((acc, cur) => acc + cur, 0);
    answer.push(sum);
  }

  return answer;
}

모범 코드


function solution(N, K, arr, queries) {
 arr.sort((a, b) => a - b);

  // arr에서 target 이상이 처음 등장하는 인덱스
  function lowerBound(target) {
    let l = 0, r = arr.length;
	    while (l < r) {
      const m = Math.floor((l + r) / 2);
      if (arr[m] < target) l = m + 1;
      else r = m;
    }
    return l;
  }
  // arr에서 target 초과가 처음 등장하는 인덱스
  function upperBound(target) {
    let l = 0, r = arr.length;
    while (l < r) {
      const m = Math.floor((l + r) / 2);
      if (arr[m] <= target) l = m + 1;
      else r = m;
    }
    return l;
  }

  const result = [];
  for (const [X, Y] of queries) {
    const left = lowerBound(X);
    const right = upperBound(Y);
    result.push(right - left);
  }
  return result;
}

세금

1️⃣ 문제

2️⃣ 문제 해결 전략

3️⃣ 코드 및 설명

4️⃣ 시간복잡도