99클럽 코테 스터디 22일차 TIL + 완전탐색

피로도

• https://school.programmers.co.kr/learn/courses/30/lessons/87946

오답노트

• 모든 상황을 고려했는가
  • 완전탐색이라면서 그리디로 풀지는 않았는지,,,ㅎ
  • 그래서 정확도가 떨어지지 않았는지,,,,

코드

function makeAllCase(arr, len) {
  if (len === 1) return arr.map((v) => [v]);

  const result = [];

  arr.forEach((f, i, o) => {
    const rest = [...o.slice(0, i), ...o.slice(i + 1)];
    const cases = makeAllCase(rest, len - 1);
    const newCases = cases.map((el) => [f, ...el]);
    result.push(...newCases);
  });

  return result;
}

function solution(k, dungeons) {
  let maxCount = 0;
  const allCases = makeAllCase(dungeons, dungeons.length);

  allCases.forEach((cases) => {
    let currentK = k;
    let count = 0;

    for (const [r, m] of cases) {
      if (currentK >= r) {
        currentK -= m;
        count += 1;
      }
    }

    maxCount = Math.max(maxCount, count);
  });

  return maxCount;
}

실패했던 코드

function solution(k, dungeons) {
  let cnt = 0;
  const copy = dungeons.slice(0).sort((a, b) => b[0] - a[0]);

  while (copy.length > 0) {
    const [r, u] = copy[0];
    if (k < r) break;

    if (k === r) {
      copy.shift();
      k -= u;
    } else {
      const [, mu] = copy.sort((a, b) => a[1] - b[1]).shift();
      k -= mu;
    }
    cnt += 1;
  }

  return cnt;
}