[프로그래머스/c++] Lv2 할인 행사

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

프로그래머스

unordered_map을 사용해서 풀었다. 시간복잡도를 위해..

자세한 설명은 코드에

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

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;

    unordered_map<string, int> wantMap;
    //map에 want, number 삽입
    for (int i = 0; i < want.size(); i++) {
        wantMap[want[i]] = number[i];
    }
    for (int i = 0; i <= discount.size() - 10; i++) {
        unordered_map<string, int> tempMap = wantMap;  //tempMap을 만들어서 항상 wantMap으로 초기화한다. 
        bool isValid = true;  //유효성 검사
        
        for (int j = i; j < i + 10; j++) {
            //만약 tempMap에서 discount[j]를 찾으면 tempMap[discount[j]]를 -- 해준다.
            if (tempMap.find(discount[j]) != tempMap.end()) {
                tempMap[discount[j]]--;
            }
            //만약 0보다 작으면 이미 없는 물건이기 때문에 false를 return 한다. 
            if (tempMap[discount[j]] < 0) {
                isValid = false;
                break;
            }
        }
        //위의 조건을 모두 만족시킬 경우
        if (isValid) {
            //number가 모두 0이어야 문제 정답이기 때문에 만약 0보다 큰 number가 있으면 false
            
            for (auto& pair : tempMap) {
                if (pair.second > 0) {
                    isValid = false;
                    break;
                }
            }
            //정말 최종적으로 isValid가 true라면 answer++
            if (isValid)
                answer++;
        }
    }

    return answer;
}