프로그래머스 레벨2 <할인 행사> C++ 풀이

discount의 구간을 앞에서 부터 10개씩 잘라가면서 각 구간에서 내가 사려고 하는 물품들을 전부 살수 있으면 카운트를 하나씩 늘려주는게 가장 먼저 떠오른 풀이방법이었습니다. 완전탐색의 방식이기 때문에 시간복잡도를 반드시 확인 해봐야죠. 만약 입력값이 크다면 완전탐색이 아닌 다른 방식의 풀이로 풀라는 의미입니다.

 

이 문제는 최대 입력값이 100,000이고 각 구간마다 10번씩 탐색하기에 시간초과에는 걸리지 않을거라 판단하고 완전탐색으로 돌렸습니다. 내가 사려고 하는 물품들에 대한 정보는 map<string,int>로 저장해두고 하나씩 줄이면서 모든 탐색이 끝나고 사려고하는 모든 물품의 갯수가 0보다 작거나 같으면 카운트를 ++해줬습니다.

 

 

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
//완탐이냐 아니냐.
 
int answer = 0;
 
void check(int idx,vector<string>& discount,map<string,int> buy)
{
    int curIdx = idx;
    
    for (int i=0;i<10;i++)
    {
        if (curIdx >= discount.size())
            return;
        
        string tmp = discount[curIdx];
        buy[tmp]--;
        curIdx++;
    }
    
    bool flag = true;
    for(auto it=buy.begin();it != buy.end();it++)
    {
        if (it->second > 0)
        {
            flag = false;
            break;
        }
    }
    
    if (flag == true)
        answer++;    
}
 
int solution(vector<string> want, vector<int> number, vector<string> discount) {
    
    
    map<string,int> buy;
    
    for (int i=0;i<want.size();i++)
    {
        buy[want[i]] = number[i];
    }
    
    for (int i=0;i<discount.size();i++)
    {   
        check(i,discount,buy);
    }
    
    return answer;
}