할인 행사

https://school.programmers.co.kr/learn/courses/30/lessons/131127

 

🔎문제 분석

구매 희망 목록과 수량이 나눠져 있어서 unodered_map 컨테이너에 저장해, 어떤 아이템을 몇 개 구매할건지 빠르게 찾을 수 있도록 저장하려했다.

할인목록 discount 역시 10일 단위로 묶어서 unordered_map에 저장하여, 10일 동안 어떤 아이템이 몇 번 할인되는지 빠르게 검색할 수 있다고 판단했다.

discount의 1일차부터 10일까지를 dicount list에 등록하고 buy list와 수량을 비교하여, buy list의 수량보다 discount list의 수량이 작은 아이템이 하나라도 있는지 확인하고, 없다면 answer의 값을 증가시켜주도록 하고,
첫째 날 확인이 끝나면 discount 할인 일정에서 1일차를 discount list에서 제거하고 11일차를 추가하는 방법 즉, 슬라이딩 윈도우 이동으로 10일씩 묶어서 확인해 나가면 데이터 삽입/삭제를 최소화할 수 있을 것으로 기대하였다.

 

✅ 구현 코드

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) 
{
    // want와 number를 map으로 합쳐서 정리 buylist
    unordered_map<string, int> buylist;
    for (int i = 0; i < want.size(); ++i)
    {
        buylist[want[i]] = number[i];
    }


    // discount목록 map에 첫 째날 부터 10일치 넣기 discountlist
    unordered_map<string, int> discountlist;
    for (int i = 0; i < 10; ++i)
    {
        discountlist[discount[i]]++;
    }

    // buylist를 순회하며 discountlist의 값보다 큰 값이 하나라도 나오면 구매불가, 모두 작거나 같으면 구매가능 -> anwer 증가
    int answer = 0;
    for (int i = 0; i <= discount.size() - 10; ++i)
    {
        bool canbuy = true;

        for (const auto& item : buylist)
        {
            if (item.second > discountlist[item.first])
            {
                canbuy = false;
                break;
            }
        }

        if (canbuy) answer++;

        if (i + 10 < discount.size())
        {
            discountlist[discount[i]]--;
            discountlist[discount[i + 10]]++;
        }
    }

    return answer;
}