본문으로 건너뛰기

작성일 : 2024.11.23

XYZ 마트 할인 행사 문제

문제 설명​

XYZ 마트에서는 10일 회원권을 구매하면 매일 하나의 제품을 할인받을 수 있습니다. 원하는 제품들을 모두 할인받을 수 있는 최적의 회원가입 시점을 찾는 문제입니다.

예시​

원하는 제품과 수량:

  • 바나나 3개
  • 사과 2개
  • 쌀 2개
  • 돼지고기 2개
  • 냄비 1개

14일간의 할인 제품:

치킨, 사과, 사과, 바나나, 쌀, 사과, 돼지고기, 바나나, 돼지고기, 쌀, 냄비, 바나나, 사과, 바나나

제한 조건​

  1. want, number 배열

    • 1 ≤ 길이 ≤ 10
    • number의 원소 합은 10
    • 각 원소 범위: 1 ≤ 원소 ≤ 10

  2. discount 배열

    • 10 ≤ 길이 ≤ 100,000
    • 원소는 알파벳 소문자
    • 원소 길이: 1 ≤ 길이 ≤ 12

해결 코드​

function solution(want, number, discount) {
  let answer = 0;
  let buyMap = new Map();
  let totalWantCount = number.reduce((acc, cur) => acc + cur, 0);

  for (let startDay = 0; startDay < discount.length; startDay++) {
    let discountList = discount.slice(startDay, startDay + totalWantCount);
    buyMap.clear();
    for (let i = 0; i < discountList.length; i++) {
      if (buyMap.has(discountList[i])) {
        buyMap.set(discountList[i], buyMap.get(discountList[i]) + 1);
      } else {
        buyMap.set(discountList[i], 1);
      }
    }
    let keyArr = [...buyMap.keys()];
    let checkCount = 0;
    for (let i = 0; i < want.length; i++) {
      if (buyMap.has(want[i]) && buyMap.get(want[i]) === number[i]) {
        checkCount++;
      }
    }
    if (checkCount === number.length) answer++;
  }
  return answer;
}

알고리즘 설명​

  1. 초기 설정

    • Map 객체로 할인 품목 카운트
    • reduce로 총 원하는 상품 개수 계산

  2. 슬라이딩 윈도우

    • 매일을 시작점으로 10일치 할인 목록 확인
    • slice로 해당 기간의 할인 목록 추출

  3. 할인 품목 카운트

    • Map을 사용해 각 품목의 개수 계산
    • 매 윈도우마다 Map 초기화(clear)

  4. 조건 확인

    • 원하는 모든 상품의 개수가 만족되는지 확인
    • 모든 조건 만족 시 answer 증가

중요 문법 요소​

  1. reduce()
// 배열의 모든 요소 합산
number.reduce((acc, cur) => acc + cur, 0);
  1. Map 메서드
// Map 초기화
buyMap.clear();

// 요소 존재 확인
buyMap.has(key);

// 요소 개수 확인
buyMap.get(key);
  1. Array 메서드
// 배열 슬라이스
discount.slice(startDay, startDay + totalWantCount)

// Map 키 배열 변환
[...buyMap.keys()]

시간 복잡도​

  • O(n * m): n은 discount 배열 길이, m은 want 배열 길이

공간 복잡도​

  • O(w): w는 want 배열 길이(Map 객체 크기)