[LeetCode] 2353. Design a Food Rating System

https://leetcode.com/problems/design-a-food-rating-system/description/

Design a Food Rating System - LeetCode

leetcode - Design a Food Rating System

문제 유형 : 해시, 정렬, 구현

문제 난이도 : Medium

 

 

문제

Design a food rating system that can do the following:

• Modify the rating of a food item listed in the system.
• Return the highest-rated food item for a type of cuisine in the system.

Implement the FoodRatings class:

• FoodRatings(String[] foods, String[] cuisines, int[] ratings) Initializes the system. The food items are described by foods, cuisines and ratings, all of which have a length of n.
  • foods[i] is the name of the ith food,
  • cuisines[i] is the type of cuisine of the ith food, and
  • ratings[i] is the initial rating of the ith food.
• void changeRating(String food, int newRating) Changes the rating of the food item with the name food.
• String highestRated(String cuisine) Returns the name of the food item that has the highest rating for the given type of cuisine. If there is a tie, return the item with the lexicographically smaller name.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

 

음식 평점 시스템을 구현하시오. 

음식의 평점을 변경할 수 있어야 합니다.

음식 종류에서 가장 높은 평점의 음식을 반환해야 합니다.

 

FoodRatings 클래스를 구현하시오:

FoodRatings(): 생성장입니다. foods, cuisiens라는 문자열배열과 ratings라는 정수 배열을 받습니다.

- foods[i]는 i번째 음식의 이름입니다.

- cuisines[i]는 i번째 음식의 종류입니다.

- ratings[i]는 i번째 음식의 초기 평점입니다.

void changeRating(food, newRating): 음식의 평점을 업데이트합니다.

String highestRated(cuisine): 주어진 종류의 음식 중 최고점을 가진 음식을 반환합니다. 만약 최고점을 가진 음식이 두 개 이상이라면, 사전순으로 앞에오는 음식을 반환합니다.

 

 

풀이

해시 테이블을 2개 만듭니다.

하나는 cuisine - set<Rating, Food>의 형태로,

하나는 food - <Rating, Cuisine>의 형태로 저장합니다. 각각 Rated, mp라고 부르겠습니다.

여기서 자료형을 편리하게 사용하기 위해서 pair<int, String>로 묶어줍시다.

set<Rating, Food>를 사용하는 이유는, set이 레드블랙트리를 이용하여 빠르게 정렬되는 자료 구조이기 때문입니다. 자바에서는 TreeSet을 사용할 수 있습니다.

오름차순형태로 자동 정렬이 됩니다.

 

 

생성자에서는 순차적으로 하나의 음식별로 해시 테이블에 작성해줍니다.

여기서, Rating을 음수로 변환하여 넣어줍시다.

set에서 자동으로 오름차순으로 정렬하기때문에, 나중에 값을 꺼낼 때 맨 앞에 있는 요소가 가장 평점이 높은 요소입니다.

게다가, 같은 평점의 경우, 이름을 사전순으로 자동 정렬해주기 때문에, rating만 음수로 넣어주면 아주 편리합니다.

 

changeRating메서드에서는 Rated의 set에서 기존 데이터를 찾아 없애줍니다.

그리고, 새로운 평점과 음식명으로 된 새로운 요소를 넣어줍니다. 여기서도 rating을 음수로 뒤집어줍니다.

이러면 평점이 새로 매겨지고, 정렬도 새로 이루어집니다.

mp에서는 단순히 평점 업데이트를 해주면 됩니다.

 

마지막으로 highestRated메서드는 Rated[cuisine]의 맨 앞 요소의 음식명을 반환해주면 됩니다.

 

 

코드

C++

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class FoodRatings {
    using item=pair<int, string>;//(rating, food), (rating, cuisine)
    unordered_map<string, set<item>> Rated;
    unordered_map<string, item> mp;
public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings)
    {
        int n=foods.size();
        for(int i=0; i<n; i++){
            string food=foods[i], cuisine=cuisines[i];
            int rating=ratings[i];
            mp[food]={-rating, cuisine};
            Rated[cuisine].insert({-rating, food});
        }
    }
    
    void changeRating(string food, int newRating) {
        string& cuisine = mp[food].second;
        int oldRating = mp[food].first;
        Rated[cuisine].erase({oldRating, food});
        Rated[cuisine].insert({-newRating, food});
        mp[food]={-newRating, cuisine};
    }
    
    string highestRated(string cuisine) {
        return Rated[cuisine].begin()->second;
    }

};

/**
 * Your FoodRatings object will be instantiated and called as such:
 * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);
 * obj->changeRating(food,newRating);
 * string param_2 = obj->highestRated(cuisine);
 */