[LeetCode 380] Insert Delete GetRandom O(1) - 효율적인 데이터 구조 구현 (Set vs. Array + Map)

[LeetCode] Insert Delete GetRandom O(1) - 효율적인 데이터 구조 구현 (Set vs. Array + Map)

문제 설명

LeetCode의 "Insert Delete GetRandom O(1)" 문제는 특정 연산을 O(1) 시간 내에 수행하는 데이터 구조를 구현하는 문제입니다.

• insert(val): 값이 없으면 추가하고 true 반환, 이미 존재하면 false 반환
• remove(val): 값이 있으면 제거하고 true 반환, 없으면 false 반환
• getRandom(): 저장된 값 중 무작위 요소를 O(1) 시간에 반환

---

📌 문제를 풀면서 생각한 과정

처음에는 Set을 사용하여 삽입과 삭제를 O(1)에 구현했지만, 무작위 요소 반환(getRandom())이 항상 첫 번째 요소만 선택되는 문제가 발생했습니다.
따라서, 배열(Array)과 해시맵(Map)을 활용하는 방식으로 최적화하였습니다.

---

📌 Set을 사용한 초기 구현 (문제점 존재)

🚨 문제점

export class RandomizedSet {
  elements: Set<number>;

  constructor() {
    this.elements = new Set<number>();
  }

  insert(val: number): boolean {
    if (this.elements.has(val)) {
      return false;
    }
    this.elements.add(val);
    return true;
  }

  remove(val: number): boolean {
    return this.elements.delete(val);
  }

  getRandom(): number {
    const val = this.elements.values().next().value;
    return val ? val : 0;
  }
}

🚨 문제점 분석

1. getRandom()이 무작위가 아님
   • this.elements.values().next().value는 항상 Set의 첫 번째 요소를 반환 → 랜덤이 아님!
   • 문제 요구사항: 무작위 요소를 선택해야 함 (O(1) 시간 복잡도 보장 필요)
2. 무작위 요소 접근 시 O(N)이 걸림
   • Set은 인덱스를 지원하지 않으므로 랜덤 요소를 찾으려면 Array.from(set)[randomIndex] 형태가 되어 O(N)이 발생

✅ 해결책: 배열(Array) + 해시맵(Map)을 활용하여 모든 연산을 O(1)로 구현

getRandom 이 1만 리턴하여 제출 실패

---

📌 배열(Array) + 해시맵(Map) 활용한 최적화된 해결법

✅ 핵심 아이디어

1. 배열(Array) 사용 → 무작위 접근(O(1))이 가능
2. 해시맵(Map) 사용 → 값을 인덱스로 저장하여 O(1) 삭제 가능
3. 삭제 시 배열 마지막 요소와 교환하여 O(1) 유지

---

📌 최적화된 코드 (O(1))

export class RandomizedSet {
  private list: number[];
  private map: Map<number, number>;

  constructor() {
    this.list = [];
    this.map = new Map<number, number>();
  }

  insert(val: number): boolean {
    if (this.map.has(val)) {
      return false;
    }

    this.list.push(val);
    this.map.set(val, this.list.length - 1);
    return true;
  }

  remove(val: number): boolean {
    if (!this.map.has(val)) {
      return false;
    }

    const index = this.map.get(val)!;
    const lastElement = this.list[this.list.length - 1];

    // 마지막 요소와 삭제할 요소 위치 변경 후 pop
    this.list[index] = lastElement;
    this.map.set(lastElement, index);

    this.list.pop();
    this.map.delete(val);

    return true;
  }

  getRandom(): number {
    const randomIndex = Math.floor(Math.random() * this.list.length);
    return this.list[randomIndex];
  }
}

---

📌 실행 예제 분석

const obj = new RandomizedSet();
console.log(obj.insert(3)); // true
console.log(obj.insert(1)); // true
console.log(obj.insert(7)); // true
console.log(obj.remove(1)); // true
console.log(obj.getRandom()); // 3 또는 7 (무작위)

✅ 배열을 활용하여 getRandom()이 무작위 동작을 수행하도록 수정 ✅ 삭제 시, O(1) 시간 복잡도를 유지하도록 최적화

---

📌 시간 및 공간 복잡도 비교

연산 원래 코드(Set 사용) 수정 코드 (배열 + 맵) 설명

insert()	O(1)	O(1)	동일
remove()	O(1)	O(1)	동일
getRandom()	O(N) (Set → 배열 변환 필요)	✅ O(1) (배열 접근 가능)	Set은 인덱스 접근 불가능

✅ 이제 getRandom()도 O(1)로 무작위 요소를 선택할 수 있음! 🚀

---

📌 Jest 테스트 코드

describe("Insert Delete GetRandom O(1)", () => {
  it("performs insert, remove, and getRandom correctly", () => {
    const obj = new RandomizedSet();
    expect(obj.insert(3)).toBe(true);
    expect(obj.insert(1)).toBe(true);
    expect(obj.insert(7)).toBe(true);
    expect(obj.remove(1)).toBe(true);
    expect([3, 7]).toContain(obj.getRandom());
  });

  it("returns false when inserting duplicates", () => {
    const obj = new RandomizedSet();
    expect(obj.insert(3)).toBe(true);
    expect(obj.insert(3)).toBe(false);
  });

  it("returns false when removing non-existent values", () => {
    const obj = new RandomizedSet();
    expect(obj.remove(5)).toBe(false);
  });
});

✅ 다양한 입력 케이스 검증하여 정확성 확보
✅ 테스트 케이스 추가 (중복 삽입, 삭제 확인)

---

📌 최종 정리

• Set을 사용하면 O(1) 삽입/삭제는 가능하지만, getRandom()이 O(N)이 됨
• 배열과 맵을 조합하면 O(1) 보장이 가능
• 무작위 요소를 빠르게 선택할 수 있도록 getRandom() 최적화

💡 이제 비슷한 문제를 만나면 "배열 + 해시맵"을 우선 고려해 보세요! 🚀