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

 이 문제는 구현 문제인 것 같다. discount의 최대 길이가 100,000이고, want의 길이가 최대 10이므로 단순 순차 검색으로도 시간 초과가 발생하지 않는다.

 

 이 문제는 단순히 요구사항들을 구현만 하면 되지만, 문제를 잘 읽어야 한다. 문제에서 요구하는 것은 가능한 일 수의 개수인데, 나는 이걸 잘못 읽어서 처음 나오는 일 수를 리턴했다. 알고리즘은 문제를 잘 읽어보는게 정말 중요한 것 같다.

 

 

 

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

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    for (int i = 0; i < discount.size() - 9; i++) {
        map<string, int> cnt;
        
        // 1. 수량 측정
        for (int j = i; j < i + 10; j++) {
            string present = discount[j];
            
            cnt[present]++;
        }
        
        bool flag = true;
        // 2. want와 비교
        for (int j = 0; j < want.size(); j++) {
            string present = want[j];
            
            if (cnt[present] != number[j]) {
                flag = false;
                break;
            }
        }
        
        if (flag) {
            answer++;
        }
    }
    
    return answer;
}