[LeetCode] 2349. Design a Number Container System (Python)

 

난이도: Medium

문제 설명

---

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.

 

제한 사항

---

• 1 <= index, number <= 109
• At most 105 calls will be made in total to change and find.

 

✏️ Solution(솔루션)

---

class NumberContainers:
    def __init__(self):
        self.container = defaultdict(SortedSet)
        self.idx = defaultdict(int)

    def change(self, index: int, number: int) -> None:
        if self.idx[index] != 0:
            self.container[self.idx[index]].remove(index)
            if not self.container[self.idx[index]]:
                del self.container[self.idx[index]]

        self.container[number].add(index)
        self.idx[index] = number

    def find(self, number: int) -> int:
        if not self.container[number]:
            return -1
        return self.container[number][0]

# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)

 

defaultdict(SortedSet)과 defaultdict(int)를 통해 해결했다.

 

change에 인자로 들어온 index가 self.idx에 있다면 self.container[self.idx[index]]에 들어가 있는 index를 지워주었다.

이때 self.container[self.idx[index]]의 리스트가 비었다면 del을 통해 아예 삭제 시켜주었다.

 

그리고 self.container[number].add(index)와 self.idx[index] = number을 통해 새로 업데이트 해주었다.

 

find는 self.container[number]가 빈 리스트이면 -1을 반환했고, 아니면 제일 작은 index인 self.container[number][0]를 반환했다.

 

---

 

처음에는 다음과 같이 heapq를 통해 진행하였는데 Wrong Answer 판정을 받았다.

import heapq
class NumberContainers:

    def __init__(self):
        self.container = {}
        self.idx = {}

    def change(self, index: int, number: int) -> None:
        if index in self.idx:
            self.container[self.idx[index]].remove(index)
            if not self.container[self.idx[index]]:
                del self.container[self.idx[index]]
        
        if number not in self.container:
            self.container[number] = []

        heapq.heappush(self.container[number], index)
        self.idx[index] = number
        

    def find(self, number: int) -> int:
        if number not in self.container:
            return -1
        x = heapq.heappop(self.container[number])
        heapq.heappush(self.container[number], x)
        return x

# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)

 

이유를 알아보다가 heapq 리스트에서 remove를 사용하면 heapq의 성질이 깨질 수 있다고 한다.

 

그러다가 알게된 것이 SortedSet이다. 이를 이용하면 제일 앞 요소가 제일 작은 값이기 때문에 좀 더 편하게 사용할 수 있었다.

---

문제: 2349. Design a Number Container System

 

깃허브: github

algorithmPractice/LeetCode/2434-design-a-number-container-system at main · laewonJeong/algorithmPractice