programmers 할인 행사

programmers

level2 할인 행사

문제 설명

위 이미지를 클릭하면 해당 문제로 이동합니다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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

    for(int i = 0; i < want.size(); i++) search_map.insert({want[i], i});    //원하는 과일의 index저장

    for(int i = 0; i <= (discount.size()-10); i++){
        vector<int> possible(want.size(), 0); //할인하는 날 중 원하는 과일 각각의 수를 기록하는 배열
        for(int j = i; j < i+10; j++){
            auto temp = search_map.find(discount[j]);
            if(temp!=search_map.end()) possible[temp->second]++;
        }
        if(possible==number) answer++;    //원하던 과일의 개수와 일치하면 증가연산자
    }

    return answer;
}

해결 과정

문자열 비교를 해야해서 map사용하려고 생각했다. 처음에는 원하는 과일의 개수를 map에 넣어주고 for루프를 돌며 감소연산자를 통해 모든 값이 0보다 작으면 answer++를 해주려고 했으나 map에 index를 저장하고 vector하나를 새로 생성하고 number와 비교해주면 될 것 같아서 그렇게 진행한 것이 위의 코드이다.

위의 코드는 해당 문제를 통과했으나 처음 생각한 방법이 맞는 방법인 것 같다. 왜냐하면 원하는 과일 이상으로 할인하여도 통과되어야 되기 때문이다.

문제 조건에 number 요소들의 합은 10이라고 주어졌기 때문에 원하는 과일의 수와 일치하게 주어지는 수 밖에 없다. 따라서 아래의 코드는 굳이 for문을 한 번 더 쓰는 것이다.

아래는 해당 문제점을 해결한 코드이다.(다만, 위의 코드도 통과되기 한다.)

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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

    for(int i = 0; i < want.size(); i++) search_map.insert({want[i], i});

    for(int i = 0; i <= (discount.size()-10); i++){
        vector<int> possible(want.size(), 0);
        int flag = 1;
        for(int j = i; j < i+10; j++){
            auto temp = search_map.find(discount[j]);
            if(temp!=search_map.end()) possible[temp->second]++;
        }
        for(int k = 0; k< want.size(); k++){
            if(number[k]>possible[k]) flag = 0;
        }
        if(flag==1) answer++;
    }

    return answer;
}