Map과 Set

Map (맵) - SortedDictionary<TKey, TValue>

 

Map은 고유한 키를 기반으로 Key-Value 쌍으로 이루어진 정렬된 자료구조입니다. C#에서는 SortedDictionary<TKey, TValue>로 구현됩니다.

 

핵심 특성

• 고유한 키: 하나의 키에 중복된 값이 들어갈 수 없음
• 자동 정렬: 삽입할 때마다 키 기준으로 자동 정렬
• 레드-블랙 트리: 균형잡힌 이진탐색트리로 구현
• O(log n) 시간복잡도: 참조, 탐색, 삽입, 삭제
• 대괄호 연산자: map[key]로 직접 참조 가능

자동 정렬의 원리

넣은 순서대로 탐색하는 것이 아닌 ASCII 코드 순으로 정렬된 값들을 기반으로 탐색합니다.

var scoreMap = new SortedDictionary<string, int>();

// 삽입 순서
scoreMap["Charlie"] = 85;
scoreMap["Alice"] = 92;    
scoreMap["Bob"] = 78;

// 실제 저장 순서 (ASCII 코드 순)
// Alice (A=65) -> Bob (B=66) -> Charlie (C=67)

foreach (var kvp in scoreMap)
{
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
}
// 출력: Alice -> Bob -> Charlie (알파벳 순)

 

 

 

중복 키 처리

var productPrices = new SortedDictionary<string, decimal>();

productPrices["laptop"] = 1200.00m;
productPrices["laptop"] = 1100.00m;  // 기존 값 덮어쓰기

Console.WriteLine(productPrices["laptop"]); // 1100.00 출력

 

Set (셋) - SortedSet<T>

 

Set은 고유한 요소만을 저장하는 자료구조입니다. 중복을 허용하지 않으며 Map처럼 자동 정렬됩니다.

 

핵심 특성

• 중복 불허: 동일한 값 중복 저장 안 함
• 자동 정렬: Map과 동일한 정렬 방식
• 레드-블랙 트리: Map과 동일한 내부 구조
• O(log n) 시간복잡도: Map과 동일한 성능

중복 제거와 자동 정렬

var numberSet = new SortedSet<int>();

// 삽입 (중복 포함)
numberSet.Add(5);
numberSet.Add(2);
numberSet.Add(8);
numberSet.Add(2);  // 중복 - 무시됨
numberSet.Add(1);

foreach (int number in numberSet)
{
    Console.Write($"{number} ");
}
// 출력: 1 2 5 8 (중복 제거 + 자동 정렬)

 

 

 

Key-Value 없이 간단한 사용

Map과 달리 Key-Value로 집어 넣지 않아도 되며, 값 자체가 식별자 역할을 합니다.

// Map: Key-Value 쌍 필요
var userScores = new SortedDictionary<string, int>();
userScores["Alice"] = 100;

// Set: 값만 저장
var uniqueUsers = new SortedSet<string>();
uniqueUsers.Add("Alice");

 

 

 

Map vs Set 동일한 메서드들

두 자료구조는 내부 구현이 동일하여 비슷한 메서드를 제공합니다:

메서드	Map	Set
Add/삽입	map[key] = value	set.Add(value)
검색	map.ContainsKey(key)	set.Contains(value)
삭제	map.Remove(key)	set.Remove(value)
개수	map.Count	set.Count
순회	foreach (var kvp in map)	foreach (var item in set)

 

Dictionary vs SortedDictionary 비교

특성	Dictionary	SortedDictionary
삽입/검색/삭제	O(1) 평균	O(log n)
정렬된 순회	불가능	O(n)
메모리 사용량	낮음	높음
구현	해시 테이블	레드-블랙 트리

 

SortedDictionary/SortedSet 사용 시기

• 정렬된 순서로 데이터 접근이 필요한 경우
• 범위 검색이 빈번한 경우
• 데이터 일관성(순서)이 중요한 경우

Dictionary/HashSet 사용 시기

• 빠른 검색 속도가 중요한 경우
• 대용량 데이터 처리 시
• 정렬이 불필요한 경우

---

실제 활용 예시

 

1. 학생 성적 관리 (Map)

var grades = new SortedDictionary<string, int>
{
    ["김철수"] = 85,
    ["이영희"] = 92, 
    ["박민수"] = 78
};

// 자동으로 이름 순 정렬되어 출력
foreach (var kvp in grades)
{
    Console.WriteLine($"{kvp.Key}: {kvp.Value}점");
}
// 출력: 김철수 -> 박민수 -> 이영희 (가나다순)

 

 

 

2. 중복 제거 (Set)

int[] numbers = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };

// 중복 제거 + 자동 정렬
var uniqueNumbers = new SortedSet<int>(numbers);

Console.WriteLine(string.Join(", ", uniqueNumbers));
// 출력: 1, 2, 3, 4, 5, 6, 9

 

 

 

3. 집합 연산 (Set)

var setA = new SortedSet<int> { 1, 3, 5, 7 };
var setB = new SortedSet<int> { 3, 5, 7, 9 };

// 교집합
var intersection = new SortedSet<int>(setA);
intersection.IntersectWith(setB);
Console.WriteLine($"교집합: {string.Join(", ", intersection)}"); // 3, 5, 7

 

 

 

레드-블랙 트리의 효율성

균형 잡힌 구조

일반 이진트리 (편향된 경우):
1
 \
  2      ← 최악의 경우 O(n)
   \
    3

레드-블랙 트리 (균형 잡힌 구조):
    2
   / \    ← 항상 O(log n) 보장
  1   3

 

 

레드-블랙 트리의 장점:

• 자가 균형: 삽입/삭제 시 자동으로 균형 조정
• 최악 성능 보장: 어떤 경우에도 O(log n) 성능 보장
• 안정적: 데이터 순서와 관계없이 일정한 성능