프로그래머스 - 할인 행사 (C++)

•  문제 자체는 이해하기 어렵지 않다. 또 주어지는 배열의 길이가 길지 않기 때문에 시간초과를 걱정할 필요가 없어 완전탐색 식으로 전부 비교해보며 풀었다. 문제 유형은 별다른 알고리즘을 요구하는 문제는 아니고 그냥 빡구현이다.

---

- 문제풀이

먼저 주어진 want 와 number를 각 맵을 이용해 넣어둔다

apple : 2

banan : 3 이런식으로 넣어둔다. 

 

그 다음 discount는 10개씩 탐색해야하므로 만약 14개의 discount 가 주어졌다면

0~9

1~10

2~11

3~12

4~13 이렇게 5번 탐색해야한다. 그러므로 discount.size() - 10 으로 범위를 잡아준다. 그리고 discount도 중복을 제외하고 맵에 넣어둔다

apple : 2

banana : 3

pork : 2 

이런식으로, 그다음 위 want의 맵과 비교해서 want를 포함하고 있다면 answer + 1 하면 된다. 총 discount - 10 번 반복하게 될 것이다.

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int days = discount.size();    
    int answer = 0;
    int tmp;
   
    map<string, int> wantthing;
    
    for(int i = 0; i < want.size(); i++)    
        wantthing.insert(make_pair(want[i], number[i]));
    
    tmp = days - 10;
 
    for(int i = 0; i < tmp+1; i++){
        map<string, int> tmpMap;
        for(int j = i; j < 10 + i; j++){
            if(tmpMap.empty()) 
                tmpMap.insert(make_pair(discount[j] , 1));
            else if(tmpMap.find(discount[j]) == tmpMap.end()) 
                tmpMap.insert(make_pair(discount[j], 1));
            else
                tmpMap[discount[j]]++;
        } 

        for(int p = 0; p < want.size(); p++){
            if(tmpMap.find(want[p]) == tmpMap.end())
                break;
            else{
                if(tmpMap[want[p]] != wantthing[want[p]])
                    break;
                else if(p == want.size() - 1)
                    answer++;
            }
        }
    }
   return answer ;
}