[Leetcode] 2353 Design a Food Rating System, C++

문제 요약

Food Rating System을 만들면 됨

접근

1. 구현

초기화

• 모든 값을 저장함 -> 새로운 값이 들어올때마다 추가함.
• cuisines[i]에 어떤 값이 들어있는지 모르므로 새로운 값이 들어올때마다 저장해야함.(unordered_map)
• cuisines[i] 마다 foods[i]와 ratings[i] 를 우선순위를 주어 저장해야함. (priority_queue) -> 점수가 같으면 사전순으로 작은 이름이 우선임

changeRating

• 새로운 값으로 바꿈
• priority_queue를 사용하므로 값을 제거하기 어려우므로 추가만하는 방향으로 진행

highestRated

• priority_queue를 사용하면 제일 위에 있는 값을 출력하면 됨.
• changeRating에서 값을 제거하지 않고 추가만 하므로 제거하는 로직 필요함 -> food마다 rating 값을 따로 저장해서(새로운 hashmap) 해당 값이랑 다르면 빼내고 다음 최상위값 확인

전체 코드

struct compare {
    bool operator() (pair<int, string> a, pair<int, string> b) 
    {
        return \
            (a.first == b.first) ?\
            (a.second>b.second) : (a.first<b.first);
    }
};

class FoodRatings {
    unordered_map<string, int> cuisineIndex;
    unordered_map<string, int> foodsRating;
    unordered_map<string, string> foodsCuisine;
    unordered_map<
        int,
        priority_queue<
            pair<int, string>,
            vector<pair<int,string>>,
            compare
        >         
    > cuisineRatings;

public:
    FoodRatings(
        vector<string>& foods,
        vector<string>& cuisines,
        vector<int>& ratings
    ) {
        for(int i=0; i < foods.size(); i++)
        {
            foodsRating[foods[i]] = ratings[i];
            foodsCuisine[foods[i]] = cuisines[i];
            if (cuisineIndex.count(cuisines[i]) == 0)
            {
                int tmpSize = cuisineRatings.size() + 1;
                cuisineRatings[tmpSize] = \
                    priority_queue<\
                        pair<int, string>,
                        vector<pair<int,string>>,
                        compare
                    > ();
                cuisineIndex[cuisines[i]] = tmpSize;
            }

            int tmpIndex = cuisineIndex.find(cuisines[i])->second;
            cuisineRatings[tmpIndex].push({ratings[i], foods[i]});
        }
    }

    void changeRating(string food, int newRating) {
        foodsRating[food] = newRating;
        string tmpCuisine = foodsCuisine[food];
        int tmpIndex = cuisineIndex.find(tmpCuisine)->second;
        cuisineRatings[tmpIndex].push({newRating, food});
    }

    string highestRated(string cuisine) {
        int tmpIndex = cuisineIndex.find(cuisine)->second;
        pair<int, string> tmpPair = cuisineRatings[tmpIndex].top();
        int tmpRate = tmpPair.first;
        string tmpFood = tmpPair.second;
        while (tmpRate != foodsRating[tmpFood])
        {
            cuisineRatings[tmpIndex].pop();
            tmpPair = cuisineRatings[tmpIndex].top();
            tmpRate = tmpPair.first;
            tmpFood = tmpPair.second;
        }

        return tmpFood;
    }
};

새로 알게된 것

1. priority_queue를 비교함수를 정의해서 사용할 때, 빈 값으로 초기화하는 것도 똑같이 해줘야함

unordered_map<int, priority_queue<pair<int, string>, vector<pair<int,string>>, compare>> cuisineRatings;

cuisineRatings[tmpSize] = priority_queue<pair<int, string>, vector<pair<int, string>>, compare> ();