[프로그래머스] - 할인 행사 with JS

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/131127?language=javascript

프로그래머스

문제 풀이

 

3중 for문으로 문제 해결하기

문제를 해결하긴 했지만 시간복잡도가 O(N^3)이여서 코드를 간결하게 할 필요가 있다.

너무 오래 걸림...!

일단 문제를 해결하는 법은 간단했다.

 

1. 배열을 계속해서 복사해서 tmp에 넣어준다. 

2.복사된 number -> tmp 값을 줄여나간다. 

만약 want 값이 discount와 같다면 tmp의 각 요소를 줄인다.

3. tmp의 값들을 확인한다.

다 줄였을 때 모든 tmp배열의 값이 0이라면?!! cnt를 1 추가해준다.

4. 반복문이 돌아갈 수 있게 , 그리고 종료될 수 있게 end, start 값을 더해준다. (종료는 discount의 길이와 같을 때)

function solution(want, number, discount) {
  let start = 0;
  let end = 10;
  let cnt = 0;

  while (end <= discount.length) {
    let tmp = [...number];

    for (let i = 0; i < want.length; i++) {
      for (let j = start; j < end; j++) {
        if (want[i] === discount[j]) {
          tmp[i]--;
        }
      }
    }

    let flag = true;
    for (let i = 0; i < tmp.length; i++) {
      if (tmp[i] > 0) {
        flag = false;
        break;
      }
    }

    if (flag) {
      cnt++;
    }

    start++;
    end++;
  }

  return cnt;
}

---

SLIDING WINDOW 로 해결하기 

과거 공부했던 방법으로 해결해보자!

2024.01.05 - [스터디/알고리즘 & 자료구조] - 알고리즘&자료구조 스터디 5주차 [Sliding Window, D&C]

알고리즘&자료구조 스터디 5주차 [Sliding Window, D&C]

function solution(want, number, discount) {
  // 윈도우의 크기 설정
  const windowSize = 10;
  let count = 0;

  // 남은 숫자와 원하는 숫자의 개수를 초기화
  let remainingNumbers = [...number];
  let wantCount = want.reduce((acc, curr) => {
    acc[curr] = (acc[curr] || 0) + 1;
    return acc;
  }, {});

  // 초기 창구의 상태를 계산
  for (let i = 0; i < windowSize; i++) {
    const item = discount[i];
    if (item in wantCount) {
      remainingNumbers[want.indexOf(item)]--;
    }
  }

  // 초기 창구에서 가능한 경우 카운트 증가
  if (remainingNumbers.every(num => num <= 0)) {
    count++;
  }

  // 슬라이딩 윈도우를 적용하여 창구의 상태를 업데이트하면서 카운트 증가
  for (let end = windowSize; end < discount.length; end++) {
    const newItem = discount[end];
    const oldItem = discount[end - windowSize];

    // 새로운 아이템이 원하는 숫자에 포함되면 남은 숫자 갱신
    if (newItem in wantCount) {
      remainingNumbers[want.indexOf(newItem)]--;
    }

    // 이전 아이템이 원하는 숫자에 포함되면 남은 숫자 복원
    if (oldItem in wantCount) {
      remainingNumbers[want.indexOf(oldItem)]++;
    }

    // 현재 창구에서 가능한 경우 카운트 증가
    if (remainingNumbers.every(num => num <= 0)) {
      count++;
    }
  }

  return count;
}

테스트1을 제외하고 많이 빨라짐!

 

꼭 시간복잡도를 줄인다고 코드가 빨라지는 것은 아니구나..!

풀 수만 있으면 된다.