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

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

프로그래머스

풀이

discount 원소 범위가 100000 이기 때문에 O(NM)을 생각했다.

알고리즘은 다음과 같다.

1. want와 number를 hash에 해싱한다. 

2. discount 항목은 10개씩 끊어서 봐야 하므로 discountHash에 먼저 9개를 해싱해둔다.

3. for문을 돌면서 i 가 증가할 때마다 discountHash에 항목을 추가해주고 hash와 비교한다.

4. 가장 앞에 추가했던 항목을 제거 해준다.

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

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    // want - number 해싱
    unordered_map<string, int> hash;
    for (int i=0; i<want.size(); i++){
        hash[want[i]] = number[i];
    }
    // discount 항목 현재 부터 9일 간의 항목 카운트 
    unordered_map<string, int> discountHash;
    for (int i=0; i<9; i++){
        discountHash[discount[i]]++;
    }
    // 추가 및 제거
    for (int i=9; i<discount.size(); i++){
        discountHash[discount[i]]++;
        // 검사
        bool ch=false;
        for (auto& i:hash){
            if (discountHash[i.first] != i.second) {
                ch=true;
                break;
            }
        }
        
        if (!ch) answer++;
        // 처음 항목 제거
        if (discountHash[discount[i-9]]>0) discountHash[discount[i-9]]--;
    }
    return answer;
}