[프로그래머스] 할인 행사

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

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

using namespace std;

bool isValid(const unordered_map <string, int>& window){
    for (auto w : window) {
        if (w.second > 0) {
            return false;
        }
    }
    
    return true;
}

int solution(vector<string> want, vector<int> number, vector<string> discount){
    
    int answer = 0;
    unordered_map <string, int> items;
    
    for(int i=0; i<want.size(); i++){
        items[want[i]] = number[i];
    }
    
    for(int i=0; i<10; i++){
        if(items.count(discount[i]) > 0){
            items[discount[i]]--;
        }
    }
    
    if(isValid(items)){
        answer++;
    }
    
    for(int i=10; i<discount.size(); i++){
        if(items.count(discount[i-10]) > 0){
            items[discount[i-10]]++;
        }
        
        if(items.count(discount[i]) > 0){
            items[discount[i]]--;
        }
        
        if(isValid(items)){
            answer++;
        }
    }
    
    return answer;
}

---

📝 풀이

이 문제를 풀 때는 슬라이딩 윈도우 기법을 사용했다.

 

먼저 items에 필요한 물건과 수량을 입력한다.

첫 날 기준으로 10일 동안 할인 품목이 items에 존재하면 수량을 감소한다.

이 과정은 첫 번째 윈도우를 초기화 하는 것이다.

 

다음은 모든 품목을 할인 받을 수 있는지 확인하는 isValid 함수를 구현한다.

windows 중 하나라도 0을 초과한다면 할인 받아야 하는 품목이 남았다는 의미로 false를 return 한다.

 

첫 번째 윈도우를 초기화 한 후 isValid 함수로 결과를 확인한다.

이후로는 윈도우를 슬라이딩하며 isValid 함수로 결과를 확인한다.

윈도우를 슬라이딩 하는 것은 다음을 의미한다.

맨 앞의 요소를 제거 👉 만약 item에 존재하던 품목이라면 👉 수량 증가

맨 뒤의 요소 추가 👉 만약 item에 존재하던 품목이라면 👉 수량 감소

 

주의할점은 모두 할인 받을 수 있는 날짜의 수를 구하는 것이다.

따라서 가능할 때마다 answer을 증가시키고 마지막까지 슬라이딩했으면 answer을 return하면 된다.