프로그래머스 할인 행사 (C++)

프로그래머스

XYZ마트는 하루 한 품목씩 10일동안 할인을 합니다. 정현이가 원하는 제품을 담은 want 배열과 제품의 수량을 나타내는 number, 그리고 할인 품목을 나타내는 discount 배열을 입력받을 때, 정현이가 원하는 제품 모두 할인 받을 수 있는 날의 총 일수를 구해주세요.

 

풀이 방법

map을 이용하여 풀이합니다. 

map<string, int> w, d;

품목의 이름, 개수를 담은 map을 두개 생성합니다. 하나는 정현이가 원하는 품목, 하나는 현재 할인중인 품목입니다.

 

for (auto p : w)
{
    string name = p.first;
    int cnt = p.second;

    if (d[name] < cnt)
    {
        find = false;
        break;
    }
}

if (find)
    answer++;

key를 통해 빠르게 탐색하는 map의 특성을 이용하여 이 둘을 빠르게 비교하는 것이 이 문제의 핵심입니다.

 

int left = 0; int right = 10;
for (int i = 0; i < discount.size() && i < 10; i++)
    d[discount[i]]++;

10일이라는 기준에 맞게 map을 세팅해주고  

 

d[discount[left++]]--;
if (right < discount.size())
    d[discount[right++]]++;

날짜가 지나면 할인 품목을 채우고 지워줍니다.

 

 

전체 코드

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) 
{
    int answer = 0;
    map<string, int> w, d;
    
    for (int i = 0; i < want.size(); i++){
        w.insert({want[i], number[i]});
        d.insert({want[i], 0});        
    }
    
    int left = 0; int right = 10;
    for (int i = 0; i < discount.size() && i < 10; i++)
        d[discount[i]]++;
    
    while (true)
    {
        bool find = true;
        for (auto p : w)
        {
            string name = p.first;
            int cnt = p.second;
            
            if (d[name] < cnt)
            {
                find = false;
                break;
            }
        }
        if (find)
            answer++;
        
        if (left >= discount.size())
            break;
        
        d[discount[left++]]--;
        if (right < discount.size())
            d[discount[right++]]++;
    }
    
    return answer;
}