[LeetCode] 2349. Design a Number Container System

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

leetcode - Design a Number Container System

문제 유형: 우선순위 큐, 힙, 해시

문제 난이도: 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.

NumberContainers 클래스를 구현하시오:

NumberContainers(): 시스템을 초기화합니다

void change(int index, int number): index번 컨테이너에 number로 채웁니다. 이미 그 인덱스에 숫자가 있다면, 그것은 버립니다.

int find(int number): 주어진 number가 들어있는 가장 작은 인덱스를 지우거나, -1을 반환하시오.

인덱스가 없으면 -1을 반환하시오.

 

풀이

두 개의 해시맵이 필요하다:

map<int, int> having: index를 키로 하고, 들어있는 number를 나타낸다.

map<int, minheap> numIdxes: number를 키로 하고, 그 숫자를 어떤 인덱스들에서 가지는지에 대해 최소힙으로 저장한다.,

 

change에서는 having[index]를 number로 넣는다.

그리고, numIdxes[number] 최소힙에 index를 삽입한다.

 

"최소 힙에 넣기만, 하고, 기존에 가지고 있던 숫자의 최소 힙 입장에서는 뺴야 하는 거 아니야?" 라는 생각이 들 수 있지만, 매 번의 change 연산마다 적용하는 것은 비효율적이다. 

대신, lazy deletion을 이용하는 것이다.

실제 find()로 조회할 때, 필요없는 데이터를 삭제할 것이다.

 

find()에서는 having[numIdxes[number].top()] != number인동안 numIdxes[number] 최소 힙에서 요소를 제거한다.

만약 최소 힙이 비어 있다면 -1을 반환하고, 아니면 최소힙의 top인 numIdxes[number].top()을 반환하면 된다.

 

코드

C++

class NumberContainers {
private:
    unordered_map<int, int> having; // having[idx] = number;
    unordered_map<int, priority_queue<int, vector<int>, greater<>>> numIdxes; // numIdxes[number].top() such that hasNum[numIdxes[number].top()] = minimum
public:
    NumberContainers() {}
    
    void change(int index, int number) {
        if (having.count(index)) {
            int lastNum = having[index];
            if (lastNum == number) return;
            having.erase(index);
        }
        having[index] = number;
        numIdxes[number].push(index);
    }
    
    int find(int number) {
        
        while(!numIdxes[number].empty() && having[numIdxes[number].top()] != number) {
            numIdxes[number].pop();
        }

        return numIdxes[number].empty()? -1 : numIdxes[number].top();
    }
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */

 

 

Go

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

type NumberContainers struct {
	having   map[int]int      
	numIdxes map[int]*MinHeap 
}

func Constructor() NumberContainers {
	return NumberContainers{
		having:   make(map[int]int),
		numIdxes: make(map[int]*MinHeap),
	}
}

func (nc *NumberContainers) Change(index int, number int) {
	if lastNum, exists := nc.having[index]; exists {
		if lastNum == number {
			return
		}
		delete(nc.having, index)
	}
	nc.having[index] = number

	if _, exists := nc.numIdxes[number]; !exists {
		nc.numIdxes[number] = &MinHeap{}
		heap.Init(nc.numIdxes[number])
	}
	heap.Push(nc.numIdxes[number], index)
}

func (nc *NumberContainers) Find(number int) int {
	if _, exists := nc.numIdxes[number]; !exists {
		return -1
	}

	for nc.numIdxes[number].Len() > 0 {
		topIdx := (*nc.numIdxes[number])[0]
		if val, exists := nc.having[topIdx]; exists && val == number {
			return topIdx
		}
		heap.Pop(nc.numIdxes[number])
	}

	return -1
}