2349. Design a Number Container System

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

 

[문제 설명]

insert, find 함수를 구현하시오.

insert(int index, int number) : 해당하는 인덱스의 number 값을 대입한다.

find(int number) : number를 가지는 인덱스 중에서 최솟값을 반환하라. 단, number에 해당하는 값이 없으면 -1을 리턴

 

[접근 방법]

1. 인덱스와 값을 구현하기 위해서 단순 배열을 사용하면 어떨까 생각

2. 그러나, 주어진 number의 최댓값이 10^9이므로 단순 배열 생성에만 10^9가 필요함.

3. map을 통해 key를 인덱스 value를 숫자로 하는 맵과 key를 숫자 value를 인덱스로 하는 map을 만듬.

-> 왜? 인덱스를 통해 값을 변경해야 하고, 값을 통해 인덱스를 검색할 수 있어야 하므로.

4. map<int, int>, map<int, int>로 구현했는데 부족한 부분이 있음. key가 숫자이고 value가 인덱스인 맵일 때 인덱스가 여러개가 될 수 있음.

-> 예 : insert(1, 10) -> insert(2, 20) -> insert(3, 10) => 값이 10일 때, value가 1과 3 두 개를 저장해야함.

만약 이후에 insert(1, 30)을 실행하면 값이 10일 땐 value는 3만 저장되야함.

5. map<int, int>, map<int, set<int>>로 변경

6. 다른 사람 답안을 보니 map이 아닌 unordered_map을 사용함. 찾아보니 unordered_map은 해싱을 이용하므로 접근 속도가 O(1)이다. 따라서, unordered_map으로 변경

#include <unordered_map>
#include <set>

class NumberContainers {
private:
    std::unordered_map<int, int> index_value_map;
    std::unordered_map<int, std::set<int>> value_index_map; // 이전 인덱스를 기억해야함. 
public:
    NumberContainers() {

    }

    void change(int index, int number) {
        // index_value_map[key]가 존재하는지 확인.
        int prev_value = index_value_map[index];
        if (prev_value == number) {
            return;
        }
        index_value_map.insert({index, number});

        value_index_map[prev_value].erase(index);
        value_index_map[number].insert(index);
    }

    int find(int number) {
        bool is_exist = value_index_map.find(number) != value_index_map.end();
        if (!is_exist || value_index_map[number].size() == 0) {
            return -1;
        }
        const auto it = value_index_map[number].begin();
        return *it;
    }
};

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

[후기]

오랜만에 풀어서 그런지 감이 잘 안온다. 문제를 처음 봤을 때는 개쉽네 하면서 접근했는데 아이디어를 잘못생각했었다.

insert로 중복해서 들어갈 때마다 이전 인덱스를 변경하거나 이전 인덱스를 지워야 하는데 이를 생각하지 못했다.

int 변수로 충분히 해결 가능하다고 생각했는데 이전 인덱스들을 저장할 필요가 있었다.

이전 인덱스들을 저장하는 것은 vector나 배열로도 충분하겠지만 접근 시간에 한계가 있기 때문에 O(1)에 접근 시간을 가지는 set을 사용했다.