할인 행사

공부하며 느낀 점

할인 행사

• 필요한 물품의 인덱스 구하기
• 하나씩 빼고 더하면서 총합이 맞춰지는지 확인하기
• 그때의 인덱스 갯수 세기?...

• 대체 왜 혜택은 15일인데 조건은 10일로해서 헷갈리게 하는 것인가?...

나의 풀이

function sol01(want, number, discount) {
  let answer = 0;
  let count = 0;
  let countObj = {};
  var discountList = new Set(discount);
  discountList = [...discountList];

  const isDiscount = want.every((item) => discountList.includes(item));

  if (!isDiscount) {
    return 0;
  }

  for (let i = 0; i < discount.length; i++) {
    count = 0;

    want.forEach((item, index) => {
      countObj[item] = number[index];
    });

    for (let j = 0; j < 10; j++) {
      const item = discount[i + j];
      if (countObj[item] > 0) {
        countObj[item]--;
        count++;

        if (count === 10) {
          answer++;
          break;
        }
      }
    }
  }

  return answer;
}

어떤거는 키와 밸류가 분리된 배열이고 어떤거는 캐 밸류가 담긴 배열이고 아주 머리가 아팠다.

아래는 countObj를 그때그때 만드는 것이 아니라 깊은복사로 구현한 것이다.

function sol02(want, number, discount) {
  let answer = 0;
  let count = 0;
  let countObjOrigin = {};
  var discountList = new Set(discount);
  discountList = [...discountList];

  const isDiscount = want.every((item) => discountList.includes(item));

  if (!isDiscount) {
    return 0;
  }

  want.forEach((item, index) => {
    countObjOrigin[item] = number[index];
  });

  for (let i = 0; i < discount.length; i++) {
    count = 0;

    const countObj = { ...countObjOrigin };

    for (let j = 0; j < 10; j++) {
      const item = discount[i + j];
      if (countObj[item] > 0) {
        countObj[item]--;
        count++;

        if (count === 10) {
          answer++;
          break;
        }
      }
    }
  }

  return answer;
}

다른 사람의 풀이

function sol1(want, number, discount) {
    let count = 0;
    for (let i = 0; i < discount.length - 9; i++) {
        const slice = discount.slice(i, i+10);

        let flag = true;
        for (let j = 0; j < want.length; j++) {
            if (slice.filter(item => item === want[j]).length !== number[j]) {
                flag = false;
                break;
            }
        }
        if (flag) count += 1;
    }
    return count;
}

내 방법과 비슷하지만 문자열을 잘라서 간다는 차이점이 있다.

속도 비교

시간 복잡도

셋다 $O(N)$이다.

  function random(max, q) {
    let arry = [];

    const multipliedE = [...q];
    for (let i = 1; i < max + 1; i++) {
      arry = [...arry, ...multipliedE];
    }

    return arry;
  }

  const q = ["banana", "apple", "rice", "pork", "pot"];
  const w = [2, 2, 2, 2, 2];
  const e = random(20, q);
  const r = random(100, e);

최악의 경우가 나오도록 세팅하였다.

반복 횟수 증가

너무나도 당연하게

필요한 만큼만 자르기 > 깊은 복사 > 그때그때 새로 만들기 순으로 빨랐다.

입력 길이 증가

모든 구간에 대해 탐색할 수 밖에 없으므로 정직하게 증가한다.

공부하며 느낀 점

1. 같은 구간을 반복해야하며, 특정 배열의 값이 변해야한다면
   • 필요한 만큼만 잘라서 배열을 만들기 > 배열을 만든다음에 깊은 복사하기 > 그때그때 새로운 배열을 만들기 순으로 빠르다.
2. 속도를 재기 위해서 배열을 반복시키는 경우가 많았는데 객체 분해할당을 사용하면 좀더 편하게 복사할 수 있다.