[Level2.] 할인 행사 C++

<< 문제 >> 

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

프로그래머스

 

 

 

저는 Hashing과 Queue를 이용해서 풀었는데

 

Hash Table에 각 품목별 개수를 일자별로 정리하는데, 이 일자별 할인품목을 queue에 보관합니다. 

 

그래서 하루가 지나면 queue의 front를 pop하고, 새 품목을 push하면서 HashTable도 최신화를 해줍니다.

 

최신화가 끝나면 HashTable에 정리된 일자별 앞으로 10일간 (할인 품목, 수)를 number와 비교하며 적절한지 파악합니다.

 

 

 

<< 코드 >>

#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    unordered_map<string,int> wantHash;
    unordered_map<string,int> discountHash;
    
    queue<string> q;
    
    for(int i = 0; i < want.size(); i++){ // Hash Table을 초기화
        wantHash[want[i]] = number[i]; // 정답지
        discountHash[want[i]] = 0;  // 각 일마다의 구매가능 상품 수 확인
    }
    
    bool isValid;
    for(int i=0; i < 10; i++){ //  1일부터 10일까지 
        if(discountHash.count(discount[i])){ // 있는 경우 1추가
            discountHash[discount[i]] = discountHash[discount[i]] + 1;
        }
        q.push(discount[i]);
        
        // 구매 가능한 날짜인지 확인 
        isValid = true;
        for(auto& c : want){
            if(wantHash[c] > discountHash[c]){
                isValid = false;
                break;
            }
        }
        if(isValid) answer++;
        // 
    }

    for(int i = 10; i < discount.size(); i++){
        
        if(discountHash.count(q.front())){
            discountHash[q.front()] = discountHash[q.front()] - 1;
        }
        q.pop();
        
        // 다음 일자로 넘어감
        q.push(discount[i]);
        if(discountHash.count(discount[i])){
            discountHash[discount[i]] = discountHash[discount[i]] + 1;
        }
        
        
        // 구매 가능한 날짜인지 확인 
        isValid = true;
        for(auto& c : want){
            if(wantHash[c] > discountHash[c]){
                isValid = false;
                break;
            }
        }
        if(isValid) answer++;
        // 
    }
    
    return answer;
}

 

 

<< GitHub >> 

 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/131127.%E2%80%85%ED%95%A0%EC%9D%B8%E2%80%85%ED%96%89%EC%82%AC