2349. Design a Number Container System / TypeScript

Design a number container system that can do the following:

• Insert or Replace a number at the given index in the system.
• Return the smallest index for the given number in the system.

Implement the NumberContainers class:

• NumberContainers() Initializes the number container system.
• void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
• int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.

 

Example 1:

Input
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output
[null, -1, null, null, null, null, 1, null, 2]

Explanation
NumberContainers nc = new NumberContainers();
nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.
nc.change(2, 10); // Your container at index 2 will be filled with number 10.
nc.change(1, 10); // Your container at index 1 will be filled with number 10.
nc.change(3, 10); // Your container at index 3 will be filled with number 10.
nc.change(5, 10); // Your container at index 5 will be filled with number 10.
nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.
nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20. 
nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.

 

출처 : https://leetcode.com/problems/design-a-number-container-system/description/

 

풀이

class NumberContainers {
  containerMap;
  valuesPQMap;
  constructor() {
    this.containerMap = new Map<number, number>();
    this.valuesPQMap = new Map<number, typeof MinPriorityQueue>();
  }

  change(index: number, num: number): void {
    const prevValue = this.containerMap.get(index);
    if (prevValue) {
      const pq = this.valuesPQMap.get(prevValue);
      if (pq.front().priority - 1 == index) {
        pq.dequeue();
      }
    }
    if (this.valuesPQMap.has(num)) {
      const newPQ = this.valuesPQMap.get(num);
      newPQ.enqueue(index, index + 1);
    } else {
      const newPQ = new MinPriorityQueue();
      newPQ.enqueue(index, index + 1);
      this.valuesPQMap.set(num, newPQ);
    }

    this.containerMap.set(index, num);
  }

  find(num: number): number {
    const newPQ = this.valuesPQMap.get(num);
    if (!newPQ) {
      return -1;
    }
    while (!newPQ.isEmpty()) {
      if (this.containerMap.get(newPQ.front().element) == num) {
        return newPQ.front().priority - 1;
      } else {
        newPQ.dequeue();
      }
    }
    return -1;
  }
}

 

특정 인덱스에 숫자를 할당하고, 해당 숫자가 할당된 가장 작은 인덱스를 찾는 함수

 

• containerMap: 인덱스를 키로 하고, 그 인덱스에 할당된 숫자를 값으로 갖는 맵.
• valuesPQMap: 숫자를 키로 하고, 해당 숫자가 할당된 인덱스들을 최소 우선순위 큐(MinPriorityQueue)로 관리하는 맵.

 

change 메서드

이 메서드는 특정 인덱스의 숫자를 변경

1. 이전 값 확인:
   • containerMap에서 주어진 index에 할당된 이전 값을 가져옴 (prevValue).
2. 이전 값 업데이트:
   • prevValue가 존재하면 (prevValue가 undefined가 아니면), valuesPQMap에서 해당 prevValue에 대한 우선순위 큐(pq)를 가져옴
   • 만약 pq의 가장 앞에 있는 요소의 우선순위가 index + 1이라면, 해당 요소를 큐에서 제거. 이는 이전 값이 변경되었기 때문에 해당 인덱스를 더 이상 유지할 필요가 없기 때문입니다.
3. 새로운 값 추가:
   • 새로 할당된 숫자(num)가 이미 valuesPQMap에 존재하는지 확인.
     • 존재하면, 해당 숫자의 우선순위 큐(newPQ)에 새로운 인덱스를 추가.
     • 존재하지 않으면, 새로운 우선순위 큐를 생성하고 인덱스를 추가한 후, valuesPQMap에 추가.
4. 맵 업데이트:
   • containerMap에 인덱스와 숫자를 업데이트하여 새로운 값을 저장.

 

change 예시 

change(1, 10);

 

• containerMap에서 index 1에 해당하는 이전 값은 없음 (prevValue는 undefined).
• valuesPQMap에 num 10에 대한 우선순위 큐가 없으므로, 새로운 큐를 만듦.
• 새 큐에 index 1을 추가하고, valuesPQMap에 (10 -> 우선순위 큐)를 저장.
• containerMap에 (1 -> 10)을 저장

containerMap = { 1: 10 }
valuesPQMap = { 10: MinPriorityQueue([{element: 1, priority: 2}]) }

 

---

change(2, 10);

 

• containerMap에서 index 2에 해당하는 이전 값은 없음 (prevValue는 undefined).
• valuesPQMap에 num 10에 대한 우선순위 큐가 있으므로, 큐에 index 2를 추가.
• containerMap에 (2 -> 10)을 저장

containerMap = { 1: 10, 2: 10 }
valuesPQMap = { 10: MinPriorityQueue([{element: 1, priority: 2}, {element: 2, priority: 3}]) }

 

---

change(1, 20);

 

• containerMap에서 index 1에 해당하는 이전 값은 10 (prevValue는 10).
• valuesPQMap에서 prevValue 10에 대한 우선순위 큐를 가져옴.
• 큐의 가장 앞에 있는 요소가 index 1이므로, 해당 요소를 큐에서 제거
• num 20에 대한 우선순위 큐가 없으므로, 새로운 큐를 만듦.
• 새 큐에 index 1을 추가하고, valuesPQMap에 (20 -> 우선순위 큐)를 저장.
• containerMap에 (1 -> 20)을 저장

containerMap = { 1: 20, 2: 10 }
valuesPQMap = { 
  10: MinPriorityQueue([{ element: 2, priority: 3 }]), 
  20: MinPriorityQueue([{ element: 1, priority: 2 }])
}

 

---

change(3, 10);

 

• containerMap에서 index 3에 해당하는 이전 값은 없음 (prevValue는 undefined).
• valuesPQMap에 num 10에 대한 우선순위 큐가 있으므로, 큐에 index 3을 추가.
• containerMap에 (3 -> 10)을 저장

containerMap = { 1: 20, 2: 10, 3: 10 }
valuesPQMap = { 
  10: MinPriorityQueue([{ element: 2, priority: 3 }, { element: 3, priority: 4 }]), 
  20: MinPriorityQueue([{ element: 1, priority: 2 }]) 
}

 

 

 

find 메서드

이 메서드는 주어진 숫자(num)가 할당된 인덱스 중 가장 작은 값을 반환

1. 우선순위 큐 가져오기:
   • valuesPQMap에서 주어진 숫자(num)에 대한 우선순위 큐(newPQ)를 가져옴.
   • 해당 숫자가 valuesPQMap에 없다면, -1을 반환. 이는 해당 숫자가 할당된 인덱스가 없음을 의미.
2. 유효한 인덱스 찾기:
   • 우선순위 큐가 비어 있지 않은 동안 반복.
     • 큐의 가장 앞에 있는 요소의 인덱스(newPQ.front().element)가 containerMap에서 주어진 숫자와 일치하는지 확인
       • 일치하면, 해당 인덱스의 우선순위에서 1을 뺀 값을 반환. (우선순위는 index + 1로 저장되었기 때문)
       • 일치하지 않으면, 해당 요소를 큐에서 제거. 이는 이전에 change 메서드로 인해 변경된 값일 수 있기 때문
3. 결과 반환:
   • 큐가 비어 있으면, -1을 반환. 이는 주어진 숫자가 할당된 유효한 인덱스가 없음을 의미

 

find 예시

 

// 초기 상태
containerMap = { 1: 20, 2: 10, 3: 10 }
valuesPQMap = { 
  10: MinPriorityQueue([{ element: 2, priority: 3 }, { element: 3, priority: 4 }]), 
  20: MinPriorityQueue([{ element: 1, priority: 2 }]) 
}

 

find(10);

 

1. 우선순위 큐 가져오기:
   • valuesPQMap에서 10에 대한 우선순위 큐 (newPQ)를 가져옴
   • newPQ = MinPriorityQueue([{ element: 2, priority: 3 }, { element: 3, priority: 4 }]);
2. 큐가 비어 있는지 확인:
   • 큐가 비어 있지 않으므로, 다음 단계로 진행
3. 큐의 맨 앞 요소 검사:
   • 큐의 맨 앞 요소는 { element: 2, priority: 3 }.
   • containerMap에서 element 2에 해당하는 값을 확인. containerMap.get(2)는 10
4. 숫자 일치 확인:
   • containerMap.get(2)의 값이 num 10과 일치
   • 따라서, newPQ.front().priority - 1을 반환
   • 여기서 priority는 3이므로 3 - 1 = 2입니다.

결과적으로, find(10)은 2를 반환

---

find(20);

1. 우선순위 큐 가져오기:
   • valuesPQMap에서 20에 대한 우선순위 큐 (newPQ)를 가져옴
   • newPQ = MinPriorityQueue([{ element: 1, priority: 2 }]);
2. 큐가 비어 있는지 확인:
   • 큐가 비어 있지 않으므로, 다음 단계로 진행.
3. 큐의 맨 앞 요소 검사:
   • 큐의 맨 앞 요소는 { element: 1, priority: 2 }입니다.
   • containerMap에서 element 1에 해당하는 값을 확인. containerMap.get(1)는 20
4. 숫자 일치 확인:
   • containerMap.get(1)의 값이 num 20과 일치
   • 따라서, newPQ.front().priority - 1을 반환. 여기서 priority는 2이므로 2 - 1 = 1

결과적으로, find(20)은 1을 반환

 

---

find(30);

1. 우선순위 큐 가져오기:
   • valuesPQMap에서 30에 대한 우선순위 큐 (newPQ)를 가져옴.
   • 30에 대한 우선순위 큐가 존재하지 않으므로, newPQ는 undefined.
2. 큐 존재 여부 확인:
   • newPQ가 undefined이므로, 숫자 30에 할당된 인덱스가 없음을 의미.

결과적으로, find(30)은 -1을 반환

 

종합

• find(10)은 2를 반환
• find(20)은 1을 반환
• find(30)은 -1을 반환

 

---

 

 

최소 우선순위 큐(MinPriorityQueue)

데이터 구조의 일종으로, 다음과 같은 두 가지 주요 기능을 제공

1. 삽입 (Enqueue): 요소를 우선순위 큐에 추가. 각 요소는 우선순위와 함께 추가되며, 우선순위가 낮을수록 더 높은 우선순위를 가짐
2. 삭제 (Dequeue): 우선순위가 가장 높은 (즉, 우선순위 값이 가장 낮은) 요소를 큐에서 제거하고 반환

작동 원리

최소 우선순위 큐는 보통 힙(Heap) 자료구조를 사용하여 구현.

이 중에서도 이진 힙(Binary Heap)을 사용하는 경우가 일반적.

1. 완전 이진 트리 속성 (Complete Binary Tree Property): 트리는 완전 이진 트리 형태를 갖추며, 모든 레벨이 꽉 채워져 있고 마지막 레벨의 경우 왼쪽부터 차례로 채워짐.
2. 힙 속성 (Heap Property): 최소 힙의 경우 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같음.

주요 연산

1. 삽입 (Enqueue)
   • 새로운 요소를 트리의 가장 마지막 위치에 추가.
   • 부모 노드와 비교하여 힙 속성을 유지하기 위해 요소를 위로 올림(상향 이동, percolate up 또는 bubble up).
2. 삭제 (Dequeue)
   • 루트 노드(가장 작은 값을 가진 노드)를 제거
   • 트리의 마지막 요소를 루트 위치로 이동
   • 자식 노드와 비교하여 힙 속성을 유지하기 위해 요소를 아래로 내림(하향 이동, percolate down 또는 bubble down).

 

 

예시

 

초기 상태:

(빈 큐)

 

삽입 (Enqueue: 5):

    5

 

삽입 (Enqueue: 3):

    3
   /
  5

 

삽입 (Enqueue: 4):

    3
   / \
  5   4

 

삭제 (Dequeue):

3이 반환되고, 4가 루트로 이동.

    4
   /
  5

 

삽입 (Enqueue: 2):

    2
   / \
  5   4