코테: 할인 행사

예시를 보면 알 수 있지만, want와 number를 dictionary 형태로 저장하면 우리가 익숙한 key와 value 양식으로 참조가 가능하다. 이를 위해 unordered_map으로 매핑을 짜 두자.

discount는 배열의 요소 개수를 세어야 하므로, discount.size()로 그 길이를 나타낸다. 할인 관련 매핑은 각각의 상품 빈도를 기록하도록 한다. 찾아보니 주어진 크기만큼 반복적으로 검색해야 할 때는 슬라이딩 윈도우 알고리즘이 유용하다고 한다.

// 첫 10일 간의 할인 제품을 discount_map에 기록
    for (int i = 0; i < 10; i++) {
        discount_map[discount[i]]++;
    }

    // 10일씩 슬라이딩 윈도우
    for (int i = 0; i <= discount.size() - 10; i++) {
        if (i > 0) {
            // 슬라이딩 윈도우로 한 칸 이동
            discount_map[discount[i - 1]]--;  // 이전 날짜의 제품 제거
            discount_map[discount[i + 9]]++;  // 새로운 날짜의 제품 추가
        }

이제 반복문에 discount_map의 상품과, want의 상품이 일치할때마다 결과에 1을 더해주면 된다.

// 현재 10일 간의 할인 제품이 정현이의 요구를 만족하는지 확인
        bool isValid = true;
        for (auto& entry : want_map) {
            if (discount_map[entry.first] < entry.second) {
                isValid = false;
                break;
            }
        }
        if (isValid) {
            answer++;
        }