[Leetcode] 2353. Design a Food Rating System, <Set vs Priority_queue>

 

 문제를 처음 접했을 때는 Priority_queue를 사용하면 풀리는 문제라고 생각하기 쉽다. 그렇지 않은가? highestRated function은 cuisine 분류 별로 제일 높은 rating을 가진 식품의 이름을 요구한다. cuisine 별로 priority_queue로 작성해 두면 쉽게 뽑아 쓸 수 있다. 그런데 문제는 바로 changeRating 함수다. 이 함수는 food의 rating을 변경하여 저장하는 것을 요구하고 있다. Priority_queue는 사용할 수 없을 것 같다. 왜?

 Priority_queue는 우선 순위대로 값을 정렬하여 보관하고 있다. 기본값은 <less>이다. 즉 내림차순으로 정렬된다는 이야기다. O(logN) operation에 삽입 정렬을 가능하게 해준다. 그런데 문제점은 indexing 접근이 어렵다는 점이다. 그렇다면 cuisine별로 저장되어 있는 food의 이름으로 값을 찾을 수 없다는 이야기다. 그렇다면 어떻게 접근해야 할까?

 정답은 이와 유사한 Set 자료 구조를 이용하는 것이다. set는 binary tree의 일종으로 red-black tree로 통상 구현되어 있다. set도 마찬가지로 값을 정렬하여 binary tree에 저장하게 되는데, 보통은 오름차순으로 정렬된다. 이 정렬 기능은 Priority_queue와 유사한 기능을 제공한다. 그런데, 다른점이라면 1) 중복된 값의 저장을 허용하지 않는 다는 점이고, 2) binary tree에 저장되어 있기 때문에 binary_search가 가능하다는 점이다. 저장된 값이 유일하기 때문에 저장된 값을 기준으로 이분 탐색을 진행하면 된다. 물론 binary tree이므로 탐색 시간은 O(logN)에 가능하다. 

 이제 큰 부분만 잡아주면 된다. food, cuisine, rating을 한 유닛으로 잡아서 저장하면 되는데, 정렬되는 방향이 rating과 food가 다르기 때문에 array<int, 3> (크기가 3인 정적 배열)을 이용할 수 없다. 우리는 구조체를 구현해야 한다. 기본 생성자는 unit으로 대입연사자 구현에 필요해서 구현해야 하며, 3개의 인자를 받는 생성자로도 구현해 준다.

struct unit{
    string food, cuisine;
    int rating;
    unit() = default;
    unit(string food, string cuisine, int rating): food(food), cuisine(cuisine), rating(rating) {}
    bool operator<(const unit& other) const {
        if(rating == other.rating) return food < other.food;
        return rating > other.rating;
    }
};

 

이러고 나면 구현의 편의 성을 위해서 food를 기준으로 indexing을 편하게 하기 위해서 <unordered_map>을 이용해서 food container를 하나 만들고, 마찬가지로 cuisine을 기준으로 분류 및 정렬하기 위해서 <unordered_map>을 이용해서 cuisine container를 만든다. 

 

unordered_map<string, unit> food_cont;
unordered_map<string, set<unit>> cuisine_cont;

 

이제는 전체적으로 구현하면 된다. 주의 해야 할 부분은 changeRating 함수에서 food의 rating 변경을 할 때, 참조자로 받아서 원본의 값이 변경될 수 있도록 해야 하며, 기존의 값은 erase함수를 통해서 손쉽게 제거하고, 마찬가지로 새로 변경된 값을 insert 내지 emplace하면 된다. 언뜻 보면 쉬워 보이지만, 코드 곳곳에 놓치기 쉬운 부분들이 많고 생각할 부분이 많아 좋은 문제라고 판단된다. 한번 풀어보길~!!

 

struct unit{
    string food, cuisine;
    int rating;
    unit() = default;
    unit(string food, string cuisine, int rating): food(food), cuisine(cuisine), rating(rating) {}
    bool operator<(const unit& other) const {
        if(rating == other.rating) return food < other.food;
        return rating > other.rating;
    }
};

class FoodRatings {
public:
    unordered_map<string, unit> food_cont;
    unordered_map<string, set<unit>> cuisine_cont;

    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for(size_t i = 0; i<size(foods); ++i) {
            food_cont[foods[i]] = unit(foods[i], cuisines[i], ratings[i]);
            cuisine_cont[cuisines[i]].emplace(foods[i], cuisines[i], ratings[i]);
        }
    }
    
    void changeRating(string food, int newRating) {
        unit& cur = food_cont[food]; // food container도 갱신을 위해서는 참조자로 받아야 한다.
        string cur_cuisine = cur.cuisine;
        cuisine_cont[cur_cuisine].erase(cur);
        cur.rating = newRating;
        cuisine_cont[cur_cuisine].emplace(cur);
    }
    
    string highestRated(string cuisine) {
        return (*begin(cuisine_cont[cuisine])).food; // iterator를 통한 값 도출 
    }
};