❓ -> ❗ 졸업 선물 : Brute Force

전혀 접근을 못하겠었는데,
'시간 복잡도 생각 1도 안하고 풀어보자' 하니까 풀렸다.

일단 어차피 나는 짬이 안되니 시간복잡도를 고려하지 말고
Brute Force로 일단 들이받는 연습을 많이 해야겠다.

Solution 풀이

function solution(m, product) {
  let answer = 0;
  let n = product.length;
  product.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));
  for (let i = 0; i < n; i++) {
    let money = m - (product[i][0] / 2 + product[i][1]);
    let cnt = 1;
    for (let j = 0; j < n; j++) {
      if (j !== i && product[j][0] + product[j][1] > money) break;
      if (j !== i && product[j][0] + product[j][1] <= money) {
        money -= product[j][0] + product[j][1];
        cnt++;
      }
    }
    answer = Math.max(answer, cnt);
  }
  return answer;
}

let arr = [
  [6, 6],
  [2, 2],
  [4, 3],
  [4, 5],
  [10, 3]
];
console.log(solution(28, arr));

내 풀이

function solution(m, product) {
  let max = Number.MIN_SAFE_INTEGER;
  for (let i in product) {
    let arr = product;
    // i 번째 선물에 쿠폰 적용
    arr[i][0] /= 2;
    arr = arr.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));
    let cnt = 0;
    let sum = 0;
    for (let x of arr) {
      if (sum >= m) {
        if (max < cnt) max = cnt;
        break;
      }
      sum += x[0] + x[1];
      cnt++;
    }
  }
  answer = max;
  return answer;
}

let arr = [
  [6, 6],
  [2, 2],
  [4, 3],
  [4, 5],
  [10, 3]
];
console.log(solution(28, arr));

내 풀이가 Solution 풀이보다 비효율적인 점

1. product 배열을 먼저 sort 했어도 됐을듯 하다.
2. 일단 할인쿠폰을 적용한 선물부터 예산에서 빼고 나머지를 카운트하는 것이
   맞는 것 같다.
   (할인쿠폰만 적용하고 실제로 사지는 못하는 경우가 카운트됐을 것 같다)

느낀 점

• 그래도 내 힘으로 Brute Force로 들이받는 시도를 성공한 것 같아서 뿌듯하다
• sort()를 잘 사용한 것 같아서 기쁘다