[Algorithm] 할인 행사 (Programmers - JavaScript)

문제 설명

XYZ 마트는 일정한 금액을 지불하면 10일 동안 회원 자격을 부여합니다. XYZ 마트에서는 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 합니다. 할인하는 제품은 하루에 하나씩만 구매할 수 있습니다. 알뜰한 정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하려 합니다.

 

예를 들어, 정현이가 원하는 제품이 바나나 3개, 사과 2개, 쌀 2개, 돼지고기 2개, 냄비 1개이며, XYZ 마트에서 15일간 회원을 대상으로 할인하는 제품이 날짜 순서대로 치킨, 사과, 사과, 바나나, 쌀, 사과, 돼지고기, 바나나, 돼지고기, 쌀, 냄비, 바나나, 사과, 바나나인 경우에 대해 알아봅시다. 첫째 날부터 열흘 간에는 냄비가 할인하지 않기 때문에 첫째 날에는 회원가입을 하지 않습니다. 둘째 날부터 열흘 간에는 바나나를 원하는 만큼 할인구매할 수 없기 때문에 둘째 날에도 회원가입을 하지 않습니다. 셋째 날, 넷째 날, 다섯째 날부터 각각 열흘은 원하는 제품과 수량이 일치하기 때문에 셋 중 하루에 회원가입을 하려 합니다.

 

정현이가 원하는 제품을 나타내는 문자열 배열 want와 정현이가 원하는 제품의 수량을 나타내는 정수 배열 number, XYZ 마트에서 할인하는 제품을 나타내는 문자열 배열 discount 가 주어졌을 때, 회원등록시 정현이가 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수를 return 하는 solution 함수를 완성하시오. 가능한 날이 없으면 0을 return 합니다.

 

 

 

---

 

 

 

 

 

 

---

 

 

 

 

 

 

---

 

 

 

 

 

 

---

 

 

 

풀이

이번 문제는 슬라이딩 윈도우 기법으로 해결했어야 했다. 슬라이딩 윈도우 기법은 배열이나 리스트와 같은 데이터 구조에서 연속적인 데이터의 부분집합을 효율적으로 처리하는 알고리즘 기법이다. 슬라이딩 윈도우의 핵심은 고정된 크기의 '윈도우(즉, 범위나 구간)'를 데이터 구조 위에 놓고, 이 윈도우를 데이터의 시작부터 끝까지 한 칸씩 이동 시키면서 윈도우 내의 데이트를 분석하거나 처리하는 것이다.

 

그렇다면 슬라이딩 윈도우 기법의 주요 특징은 무엇일까?

1) 고정된 크기의 윈도우: 윈도우의 크기는 고정되어 있으며, 이는 처리해야 할 데이터의 연속적인 부분 집합의 크기를 결정한다.

2) 순차적 이동: 윈도우는 데이터 구조를 따라 한 칸씩 순차적으로 이동한다. 각 이동에서 윈도우 내의 데이터는 분석되거나 처리된다.

3) 효율성: 윈도우가 이동할 때마다 전체 데이터를 재검사하지 않고, 윈도우에 새롭게 들어오는 데이터와 나가는 데이터만을 고려한다. 이를 통해 중복 계산을 줄이고 알고리즘의 효율성을 높힌다.

4) 다양한 용도: 슬라이딩 윈도우 기법은 최대/최소값 찾기, 평균 계산, 연속 데이터의 합계 계산 등 다양한 문제에 적용될 수 있다.

 

결론적으로, 슬라이딩 윈도우는 배열이나 리스트와 같은 순차적 데이터 구조에서 연속적인 데이터 부분집합을 처리할 때 많이 사용된다.

 

 

 

본문제로 들어가기전에 슬라이딩 윈도우의 예제를 보고 적용을 해보자.

밑에 예제는 최댓값을 찾는 방식을 적용한 슬라이딩 윈도우 예제이다.

 

밑에 코드에서 자세히 봐볼점은 [ // 슬라이딩 윈도우 ] 라고 되어있는 주석 밑에 부분이다. 

코드를 보면 loop를 0 ~ arr.length 만큼만 돌지만, 결국 [1, 2, 3], [2, 3, 4], [3, 4, 5]를 비교하고 그 비교값들 중 큰 값을 maxSum에 할당하는 코드이다. 

function maxSum(arr, windowSize) {
  let maxSum = 0;
  let tempSum = 0;
 
  // 배열 길이가 윈도우 크기보다 작은 경우
  if (arr.length < windowSize) return null;
 
  // 초기 윈도우의 합을 계산
  for (let i = 0; i < windowSize; ++i) {
    maxSum += arr[i];
  }
 
  tempSum = maxSum;
 
  // 슬라이딩 윈도우
  for (let i = windowSize; i < arr.length; ++i) {
    tempSum = tempSum - arr[i - windowSize] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
 
  return maxSum;
}
 
const arr = [1, 2, 3, 4, 5];
const windowSize = 3;
console.log(maxSum(arr, windowSize)); // 12

 

 

 

 

그렇다면, 위의 슬라이딩 윈도우를 적용해서 본문제를 풀어보자.

 

풀이에 대해서 간단하게 설명해보자면,

첫째, Map을 사용해서 key, value 형태로 원하는 제품과 그에 상응하는 숫자값을 넣은 테이블을 만들어 주었다.

 

둘째, discount의 10일치씩 검사를 해야되기 때문에 discount.length - 10를 포함하도록 적용하였다.

왜냐하면 첫날에는 0~9번 인덱스의 값을 확인할 것이고, 둘쨋날에는 1~10번 인덱스의 값을 확인할 것이고, 셋째날에는 2~11번, 넷째날에는 3~12번, 다섯째날에는 4~13번인덱스의 값을 확인해야 되기 때문이다.

결국은 제일 바깥의 for 문은 10일씩 행사했을 때 최대의 행사 날짜를 결정하기 위한 것이다.

 

셋째, j의 for문은 이제 10일치의 discount를 순회하면서 기존의 Map과 비교하는 루프이다.

j가 i부터 도는 이유는 그래야 해당 행사날짜와 행사하는 제품의 종류를 맞출 수 있기 때문이였다.

 

const discount = ["치킨", "사과", "사과", "바나나", "쌀", "사과", "돼지고기", "바나나", "돼지고기", "쌀", "냄비", "바나나", "사과", "바나나"];

 

위의 코드를 적용해보자면,

i = 0 일때는 첫날이기 때문에 ["치킨", "사과", "사과", "바나나", "쌀", "사과", "돼지고기", "바나나", "돼지고기", "쌀"] 을 확인해볼 것이고,

i = 1 일때는 둘쨋날이기 때문에 ["사과", "사과", "바나나", "쌀", "사과", "돼지고기", "바나나", "돼지고기", "쌀", "냄비"] 을 확인해볼 것이다. 

이런식으로 전부 순회를 한 후에 Map의 size === 0 일 경우가 전부 구매할 수 있는 날이기 때문에 Map.size === 0 이 되는 경우만 1씩 증가해줌으로써 몇일이 가능한지를 알 수 있는 문제였다.

 

function solution(want, number, discount) {
  let answer = 0;
  const map = new Map();
  want.forEach((el, index) => map.set(el, number[index]));
 
  for (let i = 0; i <= discount.length - 10; ++i) {
    const tempMap = new Map(map);
 
    for (let j = i; j < i + 10; ++j) {
      const check = tempMap.get(discount[j]);
 
      if (check) {
        const num = check - 1;
 
        tempMap.set(discount[j], num);
 
        if (tempMap.get(discount[j]) === 0) {
          tempMap.delete(discount[j]);
        }
      }
    }
 
    if (tempMap.size === 0) {
      answer++;
    }
  }
 
  return answer;
}