Leetcode 2349. Design a Number Container System

문제

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.

숫자 컨테이너 시스템 설계

다음 기능을 수행할 수 있는 숫자 컨테이너 시스템을 설계합니다.

• 주어진 인덱스에 숫자를 삽입하거나 교체합니다.

• 시스템에서 주어진 숫자의 가장 작은 인덱스를 반환합니다.

• NumberContainers 클래스를 구현합니다.

• NumberContainers():

  • 숫자 컨테이너 시스템을 초기화합니다.

• void change(int index, int number):

  • index 위치의 컨테이너를 number로 채웁니다. 해당 index에 이미 숫자가 있으면 교체합니다.

• int find(int number):

  • 주어진 number의 가장 작은 인덱스를 반환하고, 시스템에 number로 채워진 인덱스가 없으면 1을 반환합니다.

예제

입력

["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"][], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]

출력

[null, -1, null, null, null, null, 1, null, 2]

설명

NumberContainers nc = new NumberContainers();
nc.find(10); // 숫자 10으로 채워진 인덱스가 없으므로 -1을 반환합니다.
nc.change(2, 10); // 인덱스 2의 컨테이너가 숫자 10으로 채워집니다.
nc.change(1, 10); // 인덱스 1의 컨테이너가 숫자 10으로 채워집니다.
nc.change(3, 10); // 인덱스 3의 컨테이너가 숫자 10으로 채워집니다.
nc.change(5, 10); // 인덱스 5의 컨테이너가 숫자 10으로 채워집니다.
nc.find(10); // 숫자 10은 인덱스 1, 2, 3, 5에 있습니다. 10으로 채워진 가장 작은 인덱스는 1이므로 1을 반환합니다.
nc.change(1, 20); // 인덱스 1의 컨테이너가 숫자 20으로 채워집니다. 인덱스 1은 10으로 채워졌다가 20으로 교체되었습니다.
nc.find(10); // 숫자 10은 인덱스 2, 3, 5에 있습니다. 10으로 채워진 가장 작은 인덱스는 2이므로 2를 반환합니다.

제한

• $1 <= index, number <= 10^9$
• 모든 함수 호출은 최대 10^5 번 이루어집니다.

풀이

• 현재 숫자에 대해 어느 index에 저장되어들 있는지를 저장한다 ( MinHeap )
• 현재 index에 어떤 숫자가 저장되어 있는지를 저장한다 ( dict )
• 넣을땐 그냥 넣는다.
• 뺄때, Heap에서 꺼낼때, 꺼내진 index에 진짜로 해당 숫자가 있는지 확인하고, 아니면 무시한다.
  • 어차피 제한상 숫자의 추가는 10^5 번 이루어지기 때문에 여기서 무시하는 횟수도 10^5를 넘을수 없다.

class NumberContainers:

    def __init__(self):
        # 특정 숫자가 저장된 index를 Heap으로 저장한다.
        self.store = defaultdict(list)

        # 특정 index에 저장된 숫자를 표기한다.
        self.current = {}


    def change(self, index: int, number: int) -> None:
        heappush(self.store[number], index)

        self.current[index] = number

    def find(self, number: int) -> int:

        if len(self.store[number]) == 0:
            return -1

        while self.store[number]:
        	# 이 숫자가 들어간 index의 최소 자리 찾기
            least = self.store[number][0]
            # 근데 이 자리에 진짜 이숫자가 들어 있는지 확인한다.
            if self.current[least] == number:
                return least
            else:
            # 없었으면 무시한다 ( 없앤다 )
                heappop(self.store[number])

        return -1