2353. Design a Food Rating System

• 음식점 별로 점수에 따른 heap을 만들고 음식의 점수를 수정 하면서 최고점을 가진 음식을 찾아내는 문제.

• make_heap의 사용법이 좀 헷갈렸었던 것 같다.
• make_heap은 주어진 comparator를 기준으로 max heap을 만든다.
• 따라서 점수는 오름차순, 이름은 내림차순으로 계단식 정렬하는 comparator를 만들어야 한다.
• max heap의 최대 값을 가진 요소는 vector의 첫번째 요소가 된다.
• 시간 복잡도는 이 된다.

• 새로운 객체를 생성하는 방식으로 풀어야 제 시간 안에 실행될 수 있다.
• 기존 객체를 수정하려면 매번 heap을 다시 정렬해야 하는데 작업의 수가 요소의 수 와 비슷하다고 가정하면 시간 복잡도는 가 된다.
• 그보다는 기존 객체를 찾아서 마킹 invalidate = true하고 새로운 객체를 생성하는 편이 낫다.
• 새로운 객체를 생성해서 넣을 경우 시간 복잡도는 이 된다.
• 수정될 점수와 기존 점수가 같은 경우 작업을 건너뛰는 것도 성능에 어느정도 (실행 시간 백분위 34% → 58%) 영향이 있다.

• 최고 점수를 가진 음식을 찾을 때 마킹된 음식을 제거한다.
• heap의 최고점을 가진 요소가 마킹된 음식인 경우 pop_heap을 통해서 제거한다.

• 이름 - 음식, 음식점 이름 - 음식 목록의 map을 생성할 때 key의 정렬이 필요 없으므로 unordered_map을 사용하면 유의미한 성능 향상을 이끌어낼 수 있다 (실행 시간 백분위 58% → 97%).

class FoodRatings {
public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        // make all foods
        for (int i = 0; i < foods.size(); ++i) {
            auto food = make_shared<Food>(
                Food{cuisines[i], foods[i], ratings[i]});
            all_foods[food->name] = food;
            all_cuisines[food->cuisine].push_back(food);
        }
        // make heaps for each cuisines
        for (auto& entry : all_cuisines) {
            make_heap(entry.second.begin(), entry.second.end(), compare);
        }
    }
    
    void changeRating(string food, int newRating) {
        // find food & check ratings
        auto& ptr = all_foods[food];
        if (ptr->rating == newRating) return;

        // invalidate previous food
        ptr->invalid = true;

        // create new food
        auto new_ptr = make_shared<Food>(
            Food{ptr->cuisine, ptr->name, newRating});

        // add new food
        auto& foods = all_cuisines[ptr->cuisine];
        foods.push_back(new_ptr);
        push_heap(foods.begin(), foods.end(), compare);
        all_foods[food] = new_ptr;
    }
    
    string highestRated(string cuisine) {
        auto& foods = all_cuisines[cuisine];
        // remove invalid foods from top of the heap
        while (foods[0]->invalid) {
            pop_heap(foods.begin(), foods.end(), compare);
            foods.pop_back();
        }
        return foods[0]->name;
    }

private:
    struct Food {
        string cuisine;
        string name;
        int rating;
        bool invalid = false;
    };
    using FoodPtr = shared_ptr<Food>;

    static bool compare(FoodPtr& lhs, FoodPtr& rhs) {
        return (lhs->rating != rhs->rating)
            ? lhs->rating < rhs->rating
            : lhs->name > rhs->name;
    }

    unordered_map<string, FoodPtr> all_foods;
    unordered_map<string, vector<FoodPtr>> all_cuisines;
};