Insert Delete GetRandom O(1)

[hsskey]

문제 설명 | Insert Delete GetRandom O(1)

RandomizedSet 클래스를 구현하는 문제로, 평균 O(1) 시간 복잡도로 요소의 삽입, 제거, 랜덤 선택을 수행할 수 있어야 한다.

📝 제약조건

• -2^31 <= val <= 2^31 - 1
• insert, remove, getRandom 함수는 최대 2 * 10^5번 호출됨
• getRandom 호출 시점에는 최소 하나의 요소가 존재함을 보장
• 모든 함수는 평균 O(1) 시간 복잡도를 가져야 함

💡 예시

• Input:

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]

• Output: [null, true, false, true, 2, true, false, 2]

문제 해결 과정

Step 1: 문제 이해하기

• RandomizedSet() - 빈 집합 생성
• insert(1) - 1 삽입, 없었으므로 true 반환
• remove(2) - 2 제거 시도, 없으므로 false 반환
• insert(2) - 2 삽입, 없었으므로 true 반환
• getRandom() - 1 또는 2 중 하나를 랜덤하게 반환 (동일 확률)
• remove(1) - 1 제거, 있었으므로 true 반환
• insert(2) - 2 삽입 시도, 이미 있으므로 false 반환
• getRandom() - 2만 있으므로 2 반환

Step 2: 접근 방법

시간복잡도 분석:

• insert: O(1)으로 요소 존재 유무 확인 및 삽입
• remove: O(1)으로 요소 존재 유무 확인 및 제거
• getRandom: O(1)으로 랜덤 요소 선택

자료구조 선택:

• Map: 값의 존재 여부와 배열에서의 위치(인덱스)를 O(1)에 확인하기 위함
• 배열: 랜덤 요소 선택을 O(1)에 가능하게 하기 위함

핵심 아이디어:

• 배열에서 요소 제거는 일반적으로 O(n)이지만, 제거할 요소를 배열의 마지막 요소와 교체한 후 마지막 요소를 제거하면 O(1)에 가능

Step 3: 코드 설계

1. 초기화: Map(값->인덱스)과 배열(값 저장)을 선언
2. insert 함수:
   • Map에 값이 있는지 확인
   • 없으면 Map에 (값, 배열 길이) 추가하고 배열에 값 추가
   • 결과 반환
3. remove 함수:
   • Map에 값이 있는지 확인
   • 있으면:
     • 해당 값의 인덱스를 가져옴
     • 배열의 마지막 값을 가져옴
     • 제거할 값의 위치에 마지막 값을 넣음
     • 배열에서 마지막 값을 제거(pop)
     • Map에서 마지막 값의 인덱스를 업데이트
     • Map에서 제거할 값 삭제
   • 결과 반환
4. getRandom 함수:
   • 배열에서 랜덤 인덱스 생성하여 값 반환

Step 4: 코드 구현

var RandomizedSet = function() {
    this.numMap = new Map(); // 값 -> 인덱스 매핑
    this.numList = [];       // 값 저장 배열
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    let res = !this.numMap.has(val); // 값이 없으면 true
    if (res) {
        this.numMap.set(val, this.numList.length); // 값과 인덱스 저장
        this.numList.push(val); // 배열에 값 추가
    }
    return res;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    let res = this.numMap.has(val); // 값이 있으면 true
    if (res) {
        let idx = this.numMap.get(val); // 제거할 값의 인덱스
        let lastVal = this.numList[this.numList.length - 1]; // 마지막 값
        
        this.numList[idx] = lastVal; // 제거할 위치에 마지막 값 삽입
        this.numList.pop(); // 마지막 값 제거
        this.numMap.set(lastVal, idx); // 마지막 값의 인덱스 업데이트
        this.numMap.delete(val); // 제거할 값 삭제
    }
    return res;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    return this.numList[Math.floor(Math.random() * this.numList.length)];
};