[기술 면접 코딩 인터뷰 준비] 무작위세트(RandomizedSet) 자료구조 구현 알고리즘

LeetCode 380번을 처음 열었을 때 저는 “그냥 HashSet 감싸면 되는 거 아닌가”라고 생각했습니다. 세 메서드를 평균 O(1)에 맞춰야 한다는 조건을 보기 전까지는요. 그 이후 두 번 틀리고, LeetCode 토론에서 같은 실수를 반복하는 패턴을 수도 없이 목격했습니다. 단일 자료구조로는 이 세 가지를 동시에 만족할 수 없다는 사실을 받아들이기까지 생각보다 오래 걸렸습니다.

구현해야 할 메서드

1. insert(val) — val이 없으면 삽입 후 true, 이미 있으면 false
2. remove(val) — val이 있으면 삭제 후 true, 없으면 false
3. getRandom() — 저장된 값 중 균등 확률로 하나 반환

제가 시도한 두 가지 실패 경로

// 시도 1: LinkedHashSet 단독
// insert/remove O(1) → 통과
// getRandom에서 .toArray() 호출 → O(N) → 탈락

// 시도 2: HashMap 단독
// insert/remove O(1) → 통과
// getRandom에서 키 목록 순회 필요 → O(N) → 탈락

LeetCode 커뮤니티에서도 이 두 경로가 가장 흔한 첫 번째 시도입니다. 배열은 인덱스 기반 O(1) 랜덤 접근이 가능하지만 검색이 O(N)이고, 해시맵은 존재 여부 확인이 O(1)이지만 랜덤 인덱스 접근 방법이 없습니다. 두 자료구조를 조합해야만 세 조건을 모두 만족할 수 있습니다.

풀이: HashMap + ArrayList 조합

class RandomizedSet {
    Map<Integer, Integer> map;  // value → index in list
    List<Integer> list;
    Random rand;

    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;

        int idx = map.remove(val);
        int lastVal = list.remove(list.size() - 1);

        if (list.size() != 0 && val != lastVal) {
            map.put(lastVal, idx);
            list.set(idx, lastVal);
        }
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

remove()의 핵심: swap-and-pop

ArrayList에서 중간 요소를 삭제하면 원칙적으로 O(N) 비용이 발생합니다. 이를 O(1)로 줄이는 트릭이 swap-and-pop입니다. 삭제 대상을 마지막 위치로 옮긴 뒤 마지막 원소를 제거하면 비용이 O(1)로 줄어듭니다.

제가 Wrong Answer를 받았던 두 엣지 케이스

엣지 케이스 1: 삭제 대상이 이미 마지막 원소일 때

val과 lastVal이 같은 경우 무조건 swap을 수행하면, map에서 이미 remove(val)로 지운 키를 다시 put(lastVal, idx)로 넣는 오류가 발생합니다. val != lastVal 조건이 이 케이스를 걸러냅니다.

엣지 케이스 2: 삭제 후 배열이 비어 있을 때

원소가 1개뿐일 때 remove를 호출하면 list.remove(list.size() - 1) 이후 배열이 비어 있습니다. 이 상태에서 list.set(idx, lastVal)을 호출하면 IndexOutOfBoundsException이 발생합니다. list.size() != 0 조건이 이를 막습니다.

LeetCode 커뮤니티 토론에서 가장 많이 올라오는 Wrong Answer 원인이 정확히 이 두 가지입니다. 특히 첫 번째 케이스는 코드를 빠르게 훑으면 놓치기 쉽습니다.

면접에서 실제로 유효했던 질문

RandomizedSet에 값이 0개일 때 getRandom()을 호출하면 어떻게 처리할 것인지 면접관에게 먼저 물어보는 것이 좋습니다. 저는 IllegalArgumentException을 던지는 방식으로 처리하겠다고 말했고, 면접관이 엣지 케이스를 챙긴다는 점을 긍정적으로 평가했습니다.

시간·공간 복잡도

메서드	시간 복잡도	비고
insert	O(1) 평균	HashMap put + ArrayList add
remove	O(1) 평균	swap-and-pop
getRandom	O(1)	ArrayList 인덱스 접근
공간	O(N)	map + list 모두 N개 원소 저장

자바스크립트/파이썬 면접 환경에서의 주의점

LeetCode 커뮤니티에서 JavaScript 풀이로 자주 보이는 실수는 this.map을 생성자에서 초기화하지 않고 메서드 안에서 지역 변수로 선언하는 경우입니다. 이 경우 메서드 간 상태가 공유되지 않아 모든 케이스에서 오답이 나옵니다. 자료구조 설계 문제는 반드시 생성자에서 상태를 초기화해야 합니다.