해시 테이블 이론
해시 함수는 hashCode를 통해 데이터를 해시 테이블의 인덱스로 변환합니다. 해시 충돌은 서로 다른 데이터가 동일한 인덱스에 매핑될 때 발생하며, 주로 체이닝(연결 리스트 사용) 또는 개방 주소법(다음 빈 공간 사용)으로 해결합니다. 해시 테이블은 특정 요소의 집합 존재 여부를 빠르게 확인해야 할 때 효과적입니다. 배열도 해시 테이블의 일종으로, 요소 존재 확인을 O(1) 시간에 처리할 수 있습니다.
주요 해시 컨테이너 비교
| 컬렉션 | 구현 | 순서 | 중복 | 변경 | 조회 | 삽입/삭제 |
|---|---|---|---|---|---|---|
| set | 레드-블랙 트리 | 정렬됨 | 불가 | 불가 | O(log n) | O(log n) |
| unordered_set | 해시 테이블 | 무순 | 불가 | 불가 | O(1) | O(1) |
| 매핑 | 구현 | 순서 | 키 중복 | 키 변경 | 조회 | 삽입/삭제 |
|---|---|---|---|---|---|---|
| map | 레드-블랙 트리 | 키 정렬 | 불가 | 불가 | O(log n) | O(log n) |
| unordered_map | 해시 테이블 | 무순 | 불가 | 불가 | O(1) | O(1) |
242. 유효한 애너그램
두 문자열이 서로의 애너그램인지 판별하세요. 애너그램은 문자 재배열로 다른 단어를 형성하는 관계입니다.
class Solution {
public:
bool isAnagram(string s, string t) {
int freqMap[26] = {0};
for (char ch : s) freqMap[ch - 'a']++;
for (char ch : t) freqMap[ch - 'a']--;
for (int count : freqMap)
if (count != 0) return false;
return true;
}
};349. 두 배열의 교집합
두 정수 배열에서 공통 요소를 찾아 반환하세요. 결과는 중복이 없어야 합니다.
class Solution {
public:
vector<int> intersection(vector<int>& numsA, vector<int>& numsB) {
unordered_set<int> uniqueNums(numsA.begin(), numsA.end());
unordered_set<int> common;
for (int val : numsB)
if (uniqueNums.count(val)) common.insert(val);
return vector<int>(common.begin(), common.end());
}
};202. 행복한 수
숫자의 각 자릿수 제곱합을 반복하여 1이 되면 행복한 수입니다. 무한 루프 발생 시 false를 반환하세요.
class Solution {
public:
int digitSquareSum(int n) {
int total = 0;
while (n) {
int remainder = n % 10;
total += remainder * remainder;
n /= 10;
}
return total;
}
bool isHappy(int n) {
unordered_set<int> visited;
while (n != 1) {
if (visited.count(n)) return false;
visited.insert(n);
n = digitSquareSum(n);
}
return true;
}
};1. 두 수의 합
배열에서 두 수의 합이 타겟이 되는 인덱스 쌍을 찾으세요.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> numIndexMap;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (numIndexMap.count(complement))
return {numIndexMap[complement], i};
numIndexMap[nums[i]] = i;
}
return {};
}
};