[Array/String][Medium] 380. Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1/description

 

Q. insert된 Random한 수를 출력하는 객체를 디자인 하라. 

 insert, remove, getRandom 모두 O(1)에 작동해야 한다. 

 

 

Solution. 

 좋은 문제다. 

 

 O(1)에 작동해야 하므로, hash 류를 써야 함에는 틀림없다. 

 다만, 그렇다면 random 값을 O(1)에 반환하는 것에 문제가 생긴다. 

 

 따라서 여분의 버퍼를 별도 관리 하여야 한다. 

 

 즉, dictionary를 두고, list를 별도로 둔다. 

 insert : O(1)에 넣는다. 

 getRandom : random 함수와 list를 이용해 index 접근하여 값을 O(1)에 얻는다. 

 remove : dictionary를 O(1)에 삭제 가능하다. 다만 list를 추가 과정을 거친다. 

 list를 O(1)에 제거하려면, 0번 index나 마지막 index만 가능하다. 

 따라서 대상 제거할 index를 먼저 찾고, 0번이나 마지막 index로 교체하여 그것을 제거한다. 

 제거할 index는 어떻게 O(1)에 찾는가. 

 insert 할때 index를 알 수 있으므로, 이것을 dictionary에 넣어 저장한다. 

 

 로직을 코드로 만든다. 

 

 

public class RandomizedSet 
{
    Dictionary<int, int> mDictNums = new Dictionary<int, int>();
    List<int> mNums = new List<int>();
    Random mRand = new Random();
    
    public RandomizedSet() {
        mDictNums.Clear();
        mNums.Clear();
    }
    public bool Insert(int val) {
        if(!mDictNums.ContainsKey(val))
        {
            mDictNums.Add(val, mNums.Count);
            mNums.Add(val);
            return true;
        }
        return false;
    }
    public bool Remove(int val) {
        if(mDictNums.ContainsKey(val))
        {
            // DebugPrint();
            int idx = mDictNums[val];
            mNums[idx] = mNums[mNums.Count-1];
            mDictNums[mNums[mNums.Count-1]] = idx;
            mNums.RemoveAt(mNums.Count-1);
            mDictNums.Remove(val);
            // DebugPrint();
            return true;
        }
        return false;
    }
    public int GetRandom() {
        int rnd = mRand.Next(mNums.Count);
        return mNums[rnd];
    }

    void DebugPrint()
    {
        Console.WriteLine("");
        for(int q = 0; q < mNums.Count; ++q)
            Console.WriteLine(mNums[q]);
    }
}

   

적절한 결과를 얻었다.