LV13 unordered_map, 계수 정렬 (unordered_map, Counting Sort)

원본 배열: [5, 2, 2, 1, 2] 카운트 배열 구성: 숫자 | 0 | 1 | 2 | 3 | 4 | 5 | 개수 | 0 | 1 | 3 | 0 | 0 | 1 | 각 숫자의 등장 횟수를 센다: - 1이 1번 등장 - 2가 3번 등장 - 5가 1번 등장

누적합 계산 과정: index 0: 0 index 1: 0 + 1 = 1 index 2: 1 + 3 = 4 index 3: 4 + 0 = 4 index 4: 4 + 0 = 4 index 5: 4 + 1 = 5 결과 배열: [0, 1, 4, 4, 4, 5]

원본 배열을 뒤에서부터 처리하여 안정 정렬 보장: 3단계 과정 (5단계별 세부 처리): 1. 숫자 2 처리: count[2]=4 → result[3]=2, count[2]=3 2. 숫자 1 처리: count[1]=1 → result[0]=1, count[1]=0 3. 숫자 2 처리: count[2]=3 → result[2]=2, count[2]=2 4. 숫자 2 처리: count[2]=2 → result[1]=2, count[2]=1 5. 숫자 5 처리: count[5]=5 → result[4]=5, count[5]=4 정렬된 값을 하나씩 담색하면서, 제 위치에다가 값을 저장한다.

#include <iostream> #include <queue> int main() { int arr[5] = { 5, 2, 2, 1, 2 }; int bucket[6] = { }; // 카운트 배열 int result[5] = { }; // 결과 배열 //1. bucket에 arr의 값을 넣어준다. for (size_t i = 0; i < 5; i++) { bucket[arr[i]]++; } //2. bucket의 값을 누적시킨다. for (size_t i = 1; i < 6; i++) { bucket[i] += bucket[i - 1]; } //3. result에 bucket의 값을 넣어준다. for (size_t i = 0; i < 5; i++) { int index = bucket[arr[i]] - 1; result[index] = arr[i]; bucket[arr[i]]--; // 같은 값의 다음 위치를 위해 감소 } // 결과 출력 std::cout << "정렬 결과: "; for (int i = 0; i < 5; i++) { std::cout << result[i] << " "; } std::cout << std::endl; return 0; }

#include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> age_map; // 삽입 age_map["Alice"] = 25; age_map.insert(std::make_pair("Bob", 30)); age_map["Bob"] = 30; age_map["Charlie"] = 22; // 값 접근 std::cout << "Alice's age: " << age_map["Alice"] << std::endl; // 존재 여부 확인 if (age_map.find("Bob") != age_map.end()) { std::cout << "Bob is in the map." << std::endl; } // 삭제 age_map.erase("Charlie"); // 전체 순회 for (const auto& pair : age_map) { std::cout << pair.first << ": " << pair.second << std::endl; } return 0; }

// 방법 1: [] 연산자 map["key"] = value; // 방법 2: insert 함수 map.insert(std::make_pair("key", value)); map.insert({"key", value}); // C++11 이후

// 방법 1: [] 연산자 (없으면 기본값으로 생성) int value = map["key"]; // 방법 2: at() 함수 (없으면 예외 발생) int value = map.at("key"); // 방법 3: find() 함수 (가장 안전) auto it = map.find("key"); if (it != map.end()) { int value = it->second; }

// 키로 삭제 map.erase("key"); // 반복자로 삭제 auto it = map.find("key"); if (it != map.end()) { map.erase(it); } // 전체 삭제 map.clear();

// 크기 확인 size_t size = map.size(); // 비어있는지 확인 bool empty = map.empty(); // 키 존재 여부 (C++20) bool exists = map.contains("key"); // 개수 세기 (0 또는 1) size_t count = map.count("key");