리트코드 - 380. Insert Delete GetRandom O(1)

리트코드 - 380. Insert Delete GetRandom O(1)

출처 - https://leetcode.com/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

RandomizedSet 클래스를 구현하세요.

RandomizedSet() - RandomizedSet 객체를 초기화합니다.
bool insert(int val) - 주어진 값 val을 집합에 삽입합니다. 값이 이미 존재하지 않으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
bool remove(int val) - 주어진 값 val이 집합에 존재하면 해당 값을 집합에서 제거합니다. 값이 존재하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
int getRandom() - 현재 요소 집합에서 무작위 요소를 반환합니다 (이 메소드가 호출될 때 적어도 하나의 요소가 존재함이 보장됩니다). 각 요소는 반환될 확률이 동일해야 합니다.

 

의사코드

Map<Integer, Integer> indexMap List<Integer> elements Random random 생성자()     indexMap = new HashMap<>()     elements = new ArrayList<>()     random = new Random() 함수 insert (int val)     if (indexMap.containsKey(val))        false 리턴     indexMap.put(val, elements.size())     elements.add(val)     true 리턴 함수 remove(int val)     if (!indexMap.containsKey(val))         false 리턴     int valIndex = indexMap.get(val)     int lastIndex = elements.size() - 1     int lastValue = elements.get(lastIndex)     elements.set(valIndex, lastValue)     indexMap.put(lastValue, valIndex)     indexMap.remove(value)     elements.remove(lastIndex)     true 리턴 함수 getRandom()     elements.get(random.nextInt(elements.size()))

 

풀이코드

class RandomizedSet {
    private final Map<Integer, Integer> indexMap;
    private final List<Integer> elements;
    private final Random random = new Random();

    public RandomizedSet() {
        indexMap = new HashMap<>();
        elements = new ArrayList<>();
    }
    
    public boolean insert(int val) {
        if (indexMap.containsKey(val)) { 
            return false;
        }
        indexMap.put(val, elements.size());
        elements.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!indexMap.containsKey(val)) {
            return false;
        }
        int valIndex = indexMap.get(val);
        int lastIndex = elements.size() - 1;

        int lastValue = elements.get(lastIndex);
        elements.set(valIndex, lastValue);
        indexMap.put(lastValue, valIndex);

        indexMap.remove(val);
        elements.remove(lastIndex);
        return true;
    }
    
    public int getRandom() {
        return elements.get(random.nextInt(elements.size()));
    }
}

 

코드설명

O(1)의 시간복잡도를 이용하여 삽입/삭제/랜덤값을 실행할 수 있는 기능을 구현해야 한다.

일반 Set을 사용하면 Index를 사용할 수 없으므로 insert나 remove시 O(n)만큼 시간이 소요된다.

따라서 이 부분을 해결하기 위해 Map과 List를 활용한다.

 

List에서는 입력값(val)들을 저장하는 역할을 하고,

Map에서는 key값으로 입력값들을 가지고, value에서는 List배열애서 인덱스를 가지고 있는다.

 

이렇게 하면 장점이 두 가지 있다.

1) 입력값이 Map의 key값으로 가지는지 바로 확인 가능. O(1)

2) 입력값이 들어왔을 때 Map을 통해 List의 인덱스를 확인 가능. O(1)

 

특히 2번의 경우 List에서 제공하는 valueOf를 사용해도 인덱스를 얻을 수 있지만, O(n)의 시간복잡도를 가지기 때문에 비효율적이다.

Map을 통해 확인하면 시간복잡도 O(1)로 확인 가능하다.

 

각 메소드의 로직은 다음과 같다.

- Insert

1. 값이 있는지 확인한다.

2. (값이 없으면)Map에 입력값을 key로, list의 크기를 value로 넣는다(= 인덱스)

3. List에 값을 추가한다.

 

- remove

1. 값이 있는지 확인한다.

2. (값이 있으면)Map에서 인덱스(valIndex)를 가져온다.

3. List에서 제일 끝 값을 가져온다.

4. List에서 인덱스(valIndex) 위치의 값을 3에서 가져온 값으로 갱신한다.

5. Map에서 key가 3에서 가져온 값을, valIndex로 갱신한다.

6. map에서 입력값을 지우고, list에서는 마지막 인덱스의 값을 지운다.

 

- random

1. List에서 랜덤인덱스 값을 선택하여 가져온다.

 

특히 remove에서 list를 index로 지우는 것이 시간을 줄이는데 중요하다.

list에서 remove메소드를 사용할 때 값을 매개변수로 받으면 O(n)이지만, 인덱스로 지우면 O(1)이기 때문이다.

 

시간복잡도 - O(1)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class RandomizedSet {
    private final Set<Integer> set;

    public RandomizedSet() {
        set = new HashSet<>();
    }
    
    public boolean insert(int val) {
        if (!set.contains(val)) {
            set.add(val);
            return true;
        }
        return false;
    }
    
    public boolean remove(int val) {
        if (set.contains(val)) {
            set.remove(val);
            return true;
        }
        return false;
    }
    
    public int getRandom() {
        return set.stream()
                .skip(new Random().nextInt(set.size()))
                .findFirst().get().intValue();
    }
}

문제에서 RandomizedSet이라고 하여 set을 사용하여 푸는 문제라고 생각해서 위 코드로 제출을 했더니, 런타임이 무려 220ms나 되었다. 상위 코드들은 20ms 정도의 시간이었다.

public int getRandom() {
    Integer[] numbers = set.toArray(new Integer[set.size()]);
    Random random = new Random();
    int randomNumber = random.nextInt(set.size());
    return numbers[randomNumber];
}

일단 getRandom에서 스트림을 사용하는 부분이 시간이 너무 잡아먹은 부분을 수정하니 110ms 정도로 줄기는 했다.

 

그렇지만 근본적으로 set을 순회하는 시간이 오래 걸려서 Map와 List 두 개의 자료형을 활용하기로 했고, 풀이코드와 같다.

 

정리

list 와 map을 사용하여 set처럼 활용하기