[LeetCode] 2353. Design a Food Rating System

donghyeok·2023년 4월 3일
0

알고리즘 문제풀이

목록 보기
109/171

문제 설명

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

문제 풀이

  • 해쉬맵 자료구조와 우선순위큐를 이용하여 풀이하였다.
  • 두가지 해쉬맵을 유지한다.

    Map<String, PriorityQueue> typeMap : 타입별로 Food 타입을 우선순위큐로 유지
    Map<String, Food> nameMap : 이름별로 Food 객체를 넣어줌

  • 각 메서드의 알고리즘은 다음과 같다.
    1. FoodRatings (음식값들 넣어주기)
      • 모든 음식의 타입별로 우선순위큐를 만들어 typeMap에 넣어준다.
      • 모든 음식의 이름별로 객체를 nameMap에 넣어준다.
    2. changeRating (특정 이름의 음식 순위 바꿔주기)
      • nameMap에서 해당 이름의 객체를 찾고 우선순위큐에서 제거한다.
      • 해당 객체의 순위를 바꿔주고 다시 우선순위큐에 넣어준다.
    3. highestRated (특정 타입의 가장 순위가 높은 음식 이름 리턴)
      • 특정 타입의 우선순위큐의 가장 앞의 값을 보고 리턴한다.

소스 코드 (JAVA)

import java.util.*;

class FoodRatings {

    public class Food implements Comparable<Food>{
        String name, type;
        int rating;

        public Food (String name, String type, int rating) {
            this.name = name;
            this.type = type;
            this.rating = rating;
        }

        @Override
        public int compareTo(Food o) {
            if (this.rating < o.rating) return 1;
            else if (this.rating > o.rating) return -1;
            else {
                return this.name.compareTo(o.name);
            }
        }
    }

    public Map<String, PriorityQueue<Food>> typeMap = new HashMap<>();
    public Map<String, Food> nameMap = new HashMap<>();

    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for (int i = 0; i < foods.length; i++) {
            Food food = new Food(foods[i], cuisines[i], ratings[i]);

            nameMap.put(foods[i], food);

            if (typeMap.containsKey(cuisines[i])) {
                typeMap.get(cuisines[i]).add(food);
            } else {
                PriorityQueue<Food> pq = new PriorityQueue<>();
                pq.add(food);
                typeMap.put(cuisines[i], pq);
            }
        }
    }

    public void changeRating(String food, int newRating) {
        Food cur = nameMap.get(food);
        PriorityQueue<Food> pq = typeMap.get(cur.type);
        pq.remove(cur);
        cur.rating = newRating;
        pq.add(cur);
    }

    public String highestRated(String cuisine) {
        return typeMap.get(cuisine).peek().name;
    }
}

/**
 * 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);
 */

0개의 댓글