[Leetcode] 2353. Design a Food Rating System

최대 2 & 10^4 개의 음식들이 주어지고 음식별로 장르와 점수가 매겨져 있다. 우리에게는 객체가 주어지고 객체의 메서드 changeRating, highestRated 두 개의 동작을 만들어야 한다.

첫번째 시도. 멍청풀이

처음엔 제약조건이 단순히 음식 배열의 길이가 10^4 이길래 N^2 연산이 걸려도 10^8이니까 O(N) 만 해줘도 되지 않나? 라고 하면서 풀었다.

class FoodRatings {
    foods = []

    constructor(foods: string[], cuisines: string[], ratings: number[]) {
        this.foods = foods.map((food, i) => ({
            name: food,
            cuisine: cuisines[i],
            rating: ratings[i]
        }))
    }

    changeRating(food: string, newRating: number): void {
        this.foods = this.foods.map((f) => {
            if (food === f.name) {
                return {
                    ...f,
                    rating: newRating
                }
            }

            return f
        })
    }

    highestRated(cuisine: string): string {
        const cuisineResult = this.foods
            .filter(food => food.cuisine === cuisine)

        const highestRating = Math.max(...cuisineResult.map(c => c.rating))

        return cuisineResult
        .filter(c => c.rating === highestRating)
        .sort((a, b) => a.name.localeCompare(b.name))[0].name
    }
}

그런데 시간초과가 난다. 왜지? 하고 생각해보니 순회에 O(N)을 쓰면서 동시에 음식의 이름을 사전순정리까지 해야 해서 시간 초과에 들어가기에 충분했다(실제로 위의 코드는 78개의 테스트 케이스 중 72개만 통과했다).

그렇다면 넣는데 O(logN)을 쓰지만 꺼낼때도 O(logN)을 쓰는 힙을 사용해야 한다. 그렇게 하면 N 개의 원소를 돌면서 정리할때도 O(NlogN), 꺼낼 때에도 O(NlogN) 이 된다.

힙의 정렬조건에 lexigographic 조건까지 추가해야 한다. 다행히도(?) 자바스크립트의 문자열은 비교 연산을 바로 할 수 있어서 한결 편하게 비교할 수 있다.

class MHeap {
  private heap: [number, string][];

  constructor() {
    this.heap = [];
  }

  size(): number {
    return this.heap.length;
  }

  push(item: [number, string]): void {
    this.heap.push(item);
    let current = this.heap.length - 1;
    let parent = Math.floor((current - 1) / 2);

    while (
      current > 0 &&
      (this.heap[current][0] < this.heap[parent][0] ||
        (this.heap[current][0] === this.heap[parent][0] &&
          this.heap[current][1] < this.heap[parent][1]))
    ) {
      [this.heap[parent], this.heap[current]] = [
        this.heap[current],
        this.heap[parent],
      ];
      current = parent;
      parent = Math.floor((current - 1) / 2);
    }
  }

  pop(): [number, string] | undefined {
    if (this.heap.length === 0) {
      return undefined;
    }
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const item = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    let current = 0;
    while (true) {
      const leftChild = 2 * current + 1;
      const rightChild = 2 * current + 2;
      let smallest = current;

      if (
        leftChild < this.heap.length &&
        (this.heap[leftChild][0] < this.heap[smallest][0] ||
          (this.heap[leftChild][0] === this.heap[smallest][0] &&
            this.heap[leftChild][1] < this.heap[smallest][1]))
      ) {
        smallest = leftChild;
      }
      if (
        rightChild < this.heap.length &&
        (this.heap[rightChild][0] < this.heap[smallest][0] ||
          (this.heap[rightChild][0] === this.heap[smallest][0] &&
            this.heap[rightChild][1] < this.heap[smallest][1]))
      ) {
        smallest = rightChild;
      }

      if (smallest !== current) {
        [this.heap[current], this.heap[smallest]] = [
          this.heap[smallest],
          this.heap[current],
        ];
        current = smallest;
      } else {
        break;
      }
    }
    return item;
  }

  peek(): [number, string] | undefined {
    return this.heap.length > 0 ? this.heap[0] : undefined;
  }
}

class FoodRatings {
  private foodRatings: Map<string, number>;
  private foodCuisines: Map<string, string>;
  private cuisineHeaps: Map<string, MHeap>;

  constructor(foods: string[], cuisines: string[], ratings: number[]) {
    this.foodRatings = new Map();
    this.foodCuisines = new Map();
    this.cuisineHeaps = new Map();

    for (let i = 0; i < foods.length; i++) {
      const food = foods[i];
      const cuisine = cuisines[i];
      const rating = ratings[i];

      this.foodRatings.set(food, rating);
      this.foodCuisines.set(food, cuisine);

      if (!this.cuisineHeaps.has(cuisine)) {
        this.cuisineHeaps.set(cuisine, new MHeap());
      }
      this.cuisineHeaps.get(cuisine)!.push([-rating, food]);
    }
  }

  changeRating(food: string, newRating: number): void {
    const cuisine = this.foodCuisines.get(food)!;
    this.foodRatings.set(food, newRating);
    this.cuisineHeaps.get(cuisine)!.push([-newRating, food]);
  }

  highestRated(cuisine: string): string {
    const heap = this.cuisineHeaps.get(cuisine)!;
    while (true) {
      const [rating, food] = heap.peek()!;
      if (-rating === this.foodRatings.get(food)) {
        return food;
      }
      heap.pop();
    }
  }
}

최소힙을 만들어서 돌려본 결과 통과했다. 특이하게도 클래스 이름을 MinHeap 으로 했더니 테스트케이스 실행 시 에러가 났다. 아무래도 채점하는 코드에 또 선언되어 있는 MinHeap 이 있는 것 같다.