1/*
2 * ν΄μ ν
μ΄λΈ (Hash Table)
3 * unordered_map, unordered_set, μΆ©λ ν΄κ²°
4 *
5 * O(1) νκ· μκ°μ νμ/μ½μ
/μμ λ₯Ό μ 곡ν©λλ€.
6 */
7
8#include <iostream>
9#include <vector>
10#include <string>
11#include <unordered_map>
12#include <unordered_set>
13#include <list>
14#include <algorithm>
15
16using namespace std;
17
18// =============================================================================
19// 1. κΈ°λ³Έ ν΄μ ν¨μ
20// =============================================================================
21
22// λ¬Έμμ΄ ν΄μ (λ€νμ ν΄μ)
23size_t polynomialHash(const string& s, size_t base = 31, size_t mod = 1e9 + 9) {
24 size_t hash = 0;
25 size_t power = 1;
26 for (char c : s) {
27 hash = (hash + (c - 'a' + 1) * power) % mod;
28 power = (power * base) % mod;
29 }
30 return hash;
31}
32
33// =============================================================================
34// 2. 체μ΄λ ν΄μ ν
μ΄λΈ ꡬν
35// =============================================================================
36
37template<typename K, typename V>
38class ChainingHashTable {
39private:
40 vector<list<pair<K, V>>> table;
41 size_t capacity;
42 size_t count;
43
44 size_t hash(const K& key) const {
45 return std::hash<K>{}(key) % capacity;
46 }
47
48public:
49 ChainingHashTable(size_t cap = 16) : capacity(cap), count(0) {
50 table.resize(capacity);
51 }
52
53 void insert(const K& key, const V& value) {
54 size_t idx = hash(key);
55 for (auto& p : table[idx]) {
56 if (p.first == key) {
57 p.second = value;
58 return;
59 }
60 }
61 table[idx].emplace_back(key, value);
62 count++;
63 }
64
65 V* get(const K& key) {
66 size_t idx = hash(key);
67 for (auto& p : table[idx]) {
68 if (p.first == key) {
69 return &p.second;
70 }
71 }
72 return nullptr;
73 }
74
75 bool remove(const K& key) {
76 size_t idx = hash(key);
77 for (auto it = table[idx].begin(); it != table[idx].end(); ++it) {
78 if (it->first == key) {
79 table[idx].erase(it);
80 count--;
81 return true;
82 }
83 }
84 return false;
85 }
86
87 size_t size() const { return count; }
88};
89
90// =============================================================================
91// 3. μ€ν μ΄λλ μ± (μ ν νμ¬)
92// =============================================================================
93
94template<typename K, typename V>
95class LinearProbingHashTable {
96private:
97 struct Entry {
98 K key;
99 V value;
100 bool occupied = false;
101 bool deleted = false;
102 };
103
104 vector<Entry> table;
105 size_t capacity;
106 size_t count;
107
108 size_t hash(const K& key) const {
109 return std::hash<K>{}(key) % capacity;
110 }
111
112public:
113 LinearProbingHashTable(size_t cap = 16) : capacity(cap), count(0) {
114 table.resize(capacity);
115 }
116
117 void insert(const K& key, const V& value) {
118 size_t idx = hash(key);
119 size_t start = idx;
120
121 do {
122 if (!table[idx].occupied || table[idx].deleted) {
123 table[idx] = {key, value, true, false};
124 count++;
125 return;
126 }
127 if (table[idx].key == key) {
128 table[idx].value = value;
129 return;
130 }
131 idx = (idx + 1) % capacity;
132 } while (idx != start);
133 }
134
135 V* get(const K& key) {
136 size_t idx = hash(key);
137 size_t start = idx;
138
139 do {
140 if (!table[idx].occupied && !table[idx].deleted) {
141 return nullptr;
142 }
143 if (table[idx].occupied && !table[idx].deleted && table[idx].key == key) {
144 return &table[idx].value;
145 }
146 idx = (idx + 1) % capacity;
147 } while (idx != start);
148
149 return nullptr;
150 }
151
152 size_t size() const { return count; }
153};
154
155// =============================================================================
156// 4. LRU μΊμ (Least Recently Used)
157// =============================================================================
158
159class LRUCache {
160private:
161 int capacity;
162 list<pair<int, int>> cache; // {key, value}
163 unordered_map<int, list<pair<int, int>>::iterator> map;
164
165public:
166 LRUCache(int cap) : capacity(cap) {}
167
168 int get(int key) {
169 if (map.find(key) == map.end()) {
170 return -1;
171 }
172 // 맨 μμΌλ‘ μ΄λ
173 cache.splice(cache.begin(), cache, map[key]);
174 return map[key]->second;
175 }
176
177 void put(int key, int value) {
178 if (map.find(key) != map.end()) {
179 // κΈ°μ‘΄ ν€ μ
λ°μ΄νΈ
180 map[key]->second = value;
181 cache.splice(cache.begin(), cache, map[key]);
182 } else {
183 // μ ν€ μ½μ
184 if ((int)cache.size() == capacity) {
185 // LRU μ κ±°
186 int lruKey = cache.back().first;
187 cache.pop_back();
188 map.erase(lruKey);
189 }
190 cache.emplace_front(key, value);
191 map[key] = cache.begin();
192 }
193 }
194};
195
196// =============================================================================
197// 5. ν΄μ νμ© λ¬Έμ λ€
198// =============================================================================
199
200// λ μμ ν©
201vector<int> twoSum(const vector<int>& nums, int target) {
202 unordered_map<int, int> map;
203 for (int i = 0; i < (int)nums.size(); i++) {
204 int complement = target - nums[i];
205 if (map.count(complement)) {
206 return {map[complement], i};
207 }
208 map[nums[i]] = i;
209 }
210 return {};
211}
212
213// μ λκ·Έλ¨ κ·Έλ£Ήν
214vector<vector<string>> groupAnagrams(vector<string>& strs) {
215 unordered_map<string, vector<string>> groups;
216
217 for (const string& s : strs) {
218 string key = s;
219 sort(key.begin(), key.end());
220 groups[key].push_back(s);
221 }
222
223 vector<vector<string>> result;
224 for (auto& p : groups) {
225 result.push_back(move(p.second));
226 }
227 return result;
228}
229
230// κ°μ₯ κΈ΄ μ°μ μμ΄
231int longestConsecutive(const vector<int>& nums) {
232 unordered_set<int> numSet(nums.begin(), nums.end());
233 int maxLen = 0;
234
235 for (int num : numSet) {
236 if (!numSet.count(num - 1)) { // μμμ
237 int currentNum = num;
238 int currentLen = 1;
239
240 while (numSet.count(currentNum + 1)) {
241 currentNum++;
242 currentLen++;
243 }
244
245 maxLen = max(maxLen, currentLen);
246 }
247 }
248
249 return maxLen;
250}
251
252// λΆλΆ λ°°μ΄ ν© = k
253int subarraySum(const vector<int>& nums, int k) {
254 unordered_map<int, int> prefixCount;
255 prefixCount[0] = 1;
256 int sum = 0;
257 int count = 0;
258
259 for (int num : nums) {
260 sum += num;
261 if (prefixCount.count(sum - k)) {
262 count += prefixCount[sum - k];
263 }
264 prefixCount[sum]++;
265 }
266
267 return count;
268}
269
270// =============================================================================
271// ν
μ€νΈ
272// =============================================================================
273
274int main() {
275 cout << "============================================================" << endl;
276 cout << "ν΄μ ν
μ΄λΈ μμ " << endl;
277 cout << "============================================================" << endl;
278
279 // 1. κΈ°λ³Έ ν΄μ ν¨μ
280 cout << "\n[1] ν΄μ ν¨μ" << endl;
281 cout << " hash(\"hello\") = " << polynomialHash("hello") << endl;
282 cout << " hash(\"world\") = " << polynomialHash("world") << endl;
283
284 // 2. 체μ΄λ ν΄μ ν
μ΄λΈ
285 cout << "\n[2] 체μ΄λ ν΄μ ν
μ΄λΈ" << endl;
286 ChainingHashTable<string, int> cht;
287 cht.insert("apple", 100);
288 cht.insert("banana", 200);
289 cht.insert("cherry", 300);
290 cout << " apple: " << *cht.get("apple") << endl;
291 cout << " banana: " << *cht.get("banana") << endl;
292
293 // 3. μ ν νμ¬ ν΄μ ν
μ΄λΈ
294 cout << "\n[3] μ ν νμ¬ ν΄μ ν
μ΄λΈ" << endl;
295 LinearProbingHashTable<string, int> lpt;
296 lpt.insert("one", 1);
297 lpt.insert("two", 2);
298 lpt.insert("three", 3);
299 cout << " one: " << *lpt.get("one") << endl;
300 cout << " size: " << lpt.size() << endl;
301
302 // 4. LRU μΊμ
303 cout << "\n[4] LRU μΊμ" << endl;
304 LRUCache lru(2);
305 lru.put(1, 1);
306 lru.put(2, 2);
307 cout << " put(1,1), put(2,2)" << endl;
308 cout << " get(1): " << lru.get(1) << endl;
309 lru.put(3, 3); // 2 μ κ±°λ¨
310 cout << " put(3,3), get(2): " << lru.get(2) << endl;
311
312 // 5. λ μμ ν©
313 cout << "\n[5] λ μμ ν©" << endl;
314 vector<int> nums = {2, 7, 11, 15};
315 auto result = twoSum(nums, 9);
316 cout << " [2,7,11,15], target=9: [" << result[0] << "," << result[1] << "]" << endl;
317
318 // 6. κ°μ₯ κΈ΄ μ°μ μμ΄
319 cout << "\n[6] κ°μ₯ κΈ΄ μ°μ μμ΄" << endl;
320 vector<int> consecutive = {100, 4, 200, 1, 3, 2};
321 cout << " [100,4,200,1,3,2]: " << longestConsecutive(consecutive) << endl;
322
323 // 7. 볡μ‘λ μμ½
324 cout << "\n[7] 볡μ‘λ μμ½" << endl;
325 cout << " | μ°μ° | νκ· | μ΅μ
|" << endl;
326 cout << " |------------|-------|-------|" << endl;
327 cout << " | μ½μ
| O(1) | O(n) |" << endl;
328 cout << " | κ²μ | O(1) | O(n) |" << endl;
329 cout << " | μμ | O(1) | O(n) |" << endl;
330
331 cout << "\n============================================================" << endl;
332
333 return 0;
334}