380 - Insert Delete GetRandom O(1) (Java)
문제
풀이
set 의 형태에서, random 값을 뽑아낼 수 있는 자료구조를 만드는 문제이다.
우선 insert 와 remove 를 O(1)에 할려면 set이나 map과 같은 자료구조는 필수적으로 필요하다.
그리고 random 값을 O(1)로 뽑아내기 위해서는 리스트나 배열이 필수적이다. 해당 배열의 사이즈를 활용해서 랜덤 인덱스를 뽑고, 그 값에 한 번에 접근할 수 있으니 말이다.
난 map 과 배열의 조합으로 문제를 해결했다.
우선 배열의 끝을 가리키는 lastIdx 를 선언하고, 이를 -1로 초기화 한다.
다음은 map인데 map<값, 배열인덱스> 로 구성할 것이다.
insert
이렇게 되면 insert 때는 매개변수로 넘어오는 값으로 이미 존재하는지 확인이 가능하고,
존재하지 않는다면 lastIdx 를 증가시킨후에 map 에 추가할 수 있다.
map에 값을 추가하였으니 배열에도 lastIdx 에 값을 업데이트 시켜준다.
random
random 도 단순하게 구현이 가능하다. 배열의 실질적인 끝을 lastIdx 가 가리키고 있으니, 그 사이 인덱스를 랜덤으로 뽑아서 접근한다음 반환해주면 끝이다.
remove
문제는 remove 이다. 일반적으로 배열에서 값을 하나 삭제한 후에 빈자리를 채우려면 뒤의 값들을 모두 앞으로 끌어와야 하기에 O(n) 의 시간이 소요된다.
때문에 이를 O(1) 로 만드는것이 중요하다.
이는 배열에서 삭제하는 값이 있는곳에 가장 뒤의 값을 치환해주는걸로 해결할 수 있다.
[3, 1, 2, 4] 라는 배열에서 [1] 을 삭제한다고 하면
[3, 4, 2, 4] 로 갱신해주는 것이다.
위와 같이 한다음에 단순히 lastIdx 를 하나 줄여주면 문제없이 remove 도 구현할 수 있다!
코드
import java.util.*;
class RandomizedSet {
public Map<Integer, Integer> map;
public int[] arr = new int[20001];
public int lastIdx;
public RandomizedSet() {
map = new HashMap<>();
lastIdx = -1;
}
// 요소가 없으면 true, 있으면 false
public boolean insert(int val) {
// if map has key, return false
if(map.containsKey(val)){
return false;
}
// if not, add val
lastIdx++;
map.put(val, lastIdx);
arr[lastIdx] = val;
return true;
}
// 요소가 있으면 true, 아니면 false
public boolean remove(int val) {
if(!map.containsKey(val)){
return false;
}
map.put(arr[lastIdx], map.get(val)); // 마지막 값의 인덱스를 새롭게 갱신한다.
arr[map.get(val)] = arr[lastIdx]; // 실제로 위치도 갱신해준다.
map.remove(val); // 그리고 기존 값은 map 에서 삭제해준다.
lastIdx--;
return true;
}
public int getRandom() {
return arr[new Random().nextInt(lastIdx+1)];
}
}