프로그래머스 할인행사 c++

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

프로그래머스

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

using namespace std;
int answer_tmp = 0;

map<string,int> ma;
vector<string> str;

void check_ma()
{
    bool check = true;
    for(int i=0; i<str.size(); i++) {
        if(ma[str[i]] != 0) {
            check = false;
        }
    }
    if(check) answer_tmp++;
}

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    // 투포인터 사용
    for(int i=0; i<want.size(); i++) {
        ma[want[i]] = number[i];
        str.push_back(want[i]);
    }
    
    for(int i=0; i<10; i++) {
        ma[discount[i]]--;
    }
    check_ma();
    
    for(int i=0; i<discount.size()-10; i++) {
        ma[discount[i+10]]--;
        ma[discount[i]]++;
        check_ma();
    }
    
    answer = answer_tmp;
    
    return answer;
}

이중 for문을 쓰면 O(n2) n = 100,000 이므로 시간초과 ! 

 

투 포인터를 사용해서 for문 한번으로 가능하게 하면 됩니다