맞춤형 구조를 설계한다는 것은 각 필요 연산이 목표 복잡도에 도달하도록 **기존 구조들을 조합(compose)**하여, 한 구조가 다른 구조의 약점을 보완하게 만드는 것입니다. 고전적 기법은 hash map을 array, heap, 또는 linked list와 짝짓는 것입니다.
요구사항: , , 을 각각 O(1)에. hash map만으로는 O(1) 무작위가 불가능하고, array만으로는 O(1) 제거가 불가능합니다. 하세요.
insert(x)remove(x)getRandom()import random
class RandomizedSet:
def __init__(self):
self.idx = {} # value -> list에서의 index
self.vals = [] # O(1) 무작위 선택을 위한 값들
def insert(self, x): # O(1)
if x in self.idx: return False
self.idx[x] = len(self.vals)
self.vals.append(x)
return True
def remove(self, x): # O(1): 마지막과 swap 후 pop
if x not in self.idx: return False
i, last = self.idx[x], self.vals[-1]
self.vals[i] = last # 마지막을 빈 자리로 이동
self.idx[last] = i
self.vals.pop()
del self.idx[x]
return True
def getRandom(self): # O(1)
return random.choice(self.vals)
1. 필요한 모든 연산 + 그 목표 복잡도를 나열한다.
2. 각각에 대해, 그것을 충족하는 구조를 지정한다:
key로 O(1) -> hash map
index로 O(1) -> array
min/max O(log n) -> heap
순서 O(log n) -> balanced tree / skip list
O(1) splice -> doubly linked list
3. 이들을 결합한다; hash map으로 key -> 위치/노드를
다른 구조에 매핑하여 갱신이 O(1)을 유지하게 한다.
4. 각 연산을 목표에 대해 검증한다.
| 패턴 | 결합한 구조 | 가능하게 하는 것 |
|---|---|---|
| LRU cache | hash map + doubly linked list | O(1) get/put |
| O(1) randomized set | hash map + array | O(1) insert/remove/random |
| stack에서 O(1) min | stack + 보조 min-stack | O(1) getMin |
실제 시스템은 단일 교과서 구조를 필요로 하는 경우가 드뭅니다. 특정 접근 패턴에 맞춰진 복합 구조가 필요하며, 이 설계들이 바로 그것을 제공합니다.
면접관은 이 문제들로 당신이 연산 비용에서 조합으로 추론할 수 있는지를 시험합니다. 이는 고성능 시스템 설계의 핵심 기술입니다.