TIL_20250430_알고리즘_슬라이딩윈도우

TIL (Today I Learned) – 귤 할인 목록 슬라이딩 윈도우 시뮬레이션 문제 정리

---

📌 학습일: 2025-04-30
📝 주제: 고정 길이 슬라이딩 윈도우 + 해시맵 카운팅을 활용해, 연속된 할인 기간 내에 원하는 상품 수량을 만족하는 구간 개수 구하기

---

1. 문제 개요

• 주어진 discount 배열에서 10일 연속 할인 상품 목록을 훑으면서
• want 목록에 적힌 각 상품이 필요한 number만큼 포함된 윈도우 구간이 총 몇 개인지 세기

---

2. 핵심 아이디어

1. 해시맵에 want[i] → number[i] 매핑
2. 슬라이딩 윈도우(크기 10)마다 해시맵 기반 카운팅
3. 각 구간의 카운트맵이 wantMap과 일치하면 answer++

---

3. 전략 요약

// 1) wantMap 생성
for (i=0; i<want.length; i++)
    wantMap.put(want[i], number[i]);

// 2) discount 배열에서 i=0~n-10 까지
for (i=0; i<=discount.length-10; i++) {
    // 2-1) windowMap 초기화 후 10일치 카운팅
    for (j=i; j<i+10; j++)
        windowMap.put(discount[j], windowMap.getOrDefault(...)+1);
    // 2-2) wantMap과 비교
    if (모두 일치) answer++;
}
return answer;

---

4. 예제

want      = ["banana","apple","rice","pork","pot"];
number    = [3,2,2,2,1];
discount  = ["chicken","apple","apple","banana","rice","apple",
             "pork","banana","pork","rice","pot","banana","apple","banana"];
// → 3개의 구간이 조건을 만족

---

5. 시간·공간 복잡도

• 시간: 외부 루프 O(N), 내부 고정 10회 → O(10·N) ≃ O(N)
• 공간: 맵 2개 사용 → O(M) (M = 서로 다른 상품 수)

---

6. 추가 최적화

• 맵을 매번 새로 생성하지 않고
  • 윈도우 이동 시 맵에서 앞 요소 카운트–1, 뒤 요소 카운트+1
  • → 완전한 리빌드 없이 O(1) 업데이트 가능한 투 포인터 기법 적용 가능

---

핵심 키워드: 슬라이딩 윈도우, 해시맵 카운팅, 투 포인터 최적화