[Leetcode] 3408. Design Task Manager

태스크 매니저를 만들어야 한다. userId, taskId, priority 세 개의 값이 주어지며 execTop() 메서드를 사용하면 모든 사용자가 가진 작업 중 priority 가 가장 높은 유저의 id 가 반환되어야 한다. 다만, 가장 높은 priority 가 여러 개 라면 가장 높은 taskId 를 가진 유저의 id 가 반환되어야 한다.

이전 문제와 마찬가지로 최대힙을 사용해야 하는 문제. taskId 를 기반으로 추가, 수정, 삭제 연산이 같이 가능해야 한다. 힙은 특정한 자료를 찾아내는 데 최적화되어 있는 자료구조가 아니다. 힙은 가져온 값이 최댓값 또는 최솟값임을 보장하는데 최적화된 자료구조이다.

따라서 별도의 해시맵을 하나 만들어준다. 수정이나 삭제 연산에서는 해시맵만 업데이트하고, execTop() 메서드 안에서 힙에 든 값을 꺼냈을 때 valid 한 값인지 해시맵으로 검증 후 내보내면 된다(힙-해시맵 이 같이 쓰이는 경우는 정말 많다).

class MyMaxHeap {
  private heap: [number, number, number, number][];

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

  push(item: [number, number, number, number]): 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, number, number, number] | 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 largest = current;

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

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

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

class TaskManager {
  private taskInfo: Map<number, { userId: number; priority: number; timeStamp: number }>;
  private maxHeap: MyMaxHeap;
  private timeStamp: number;

  constructor(tasks: number[][]) {
    this.taskInfo = new Map();
    this.maxHeap = new MyMaxHeap();
    this.timeStamp = 0;

    for (const [userId, taskId, priority] of tasks) {
      this.add(userId, taskId, priority);
    }
  }

  add(userId: number, taskId: number, priority: number): void {
    this.taskInfo.set(taskId, { userId, priority, timeStamp: this.timeStamp });
    this.maxHeap.push([priority, taskId, userId, this.timeStamp]);
    this.timeStamp += 1;
  }

  edit(taskId: number, newPriority: number): void {
    const task = this.taskInfo.get(taskId);
    if (task) {
      task.priority = newPriority;
      this.maxHeap.push([newPriority, taskId, task.userId, task.timeStamp]);
    }
  }

  rmv(taskId: number): void {
    this.taskInfo.delete(taskId);
  }

  execTop(): number {
    if (this.maxHeap.peek() === undefined) {
      return -1;
    }

    while (this.maxHeap.peek() !== undefined) {
      const [priority, taskId, userId, timeStamp] = this.maxHeap.peek()!;
      const latestTaskInfo = this.taskInfo.get(taskId);

      if (
        latestTaskInfo &&
        latestTaskInfo.priority === priority &&
        latestTaskInfo.timeStamp === timeStamp
      ) {
        this.maxHeap.pop();
        this.taskInfo.delete(taskId);
        return userId;
      } else {
        this.maxHeap.pop();
      }
    }

    return -1;
  }
}

컴중간에 부득이하게 timeStamp 라는 값을 추가했는데, 하나의 태스크를 삭제한 뒤 다른 사용자에게 재부여한 경우 힙이 최신상태를 제대로 인지하지 못해서이다.

위의 경우 userId 는 다르지만 어쨌든 한번 삭제를 했었던 taskId 가 다시 해시맵에 추가되어 존재하고 있었고, 해시맵을 기반으로 priority 만 비교하는 연산에서는 userId 업데이트를 알아차릴 수 없기 때문이었다. 실제로 [8, 101, 1], [8, 101, 50] 두 개의 값이 있는 경우 앞의 값이 먼저 나왔다(순서는 priority, taskId, userId).

timeStamp 값을 추가해서 .add() 메서드가 실행될 때 마다 찍히는 타임스탬프를 도입해 정합성 검사를 하나 더 추가해서 해결했다.