집합과 맵

집합과 맵이 푸는 문제

배열에서 "이 값이 들어 있나?"를 확인하려면 처음부터 끝까지 훑어 \(O(N)\)이 듭니다.
집합(set) 과 맵(map) 은 이 검색을 훨씬 빠르게 만들어 주는 자료구조입니다.

• 집합: 값들의 모임. 중복을 허용하지 않고, 있는지/없는지를 빠르게 확인.
• 맵: 키 → 값의 대응. "이 단어가 몇 번 나왔나"처럼 무언가를 세거나 매핑.

1. 두 가지 구현: 해시 vs 트리

해시 기반은 평균적으로 더 빠르지만 순서가 없습니다. 트리 기반은 약간 느린
대신 항상 정렬된 순서를 유지하고, "이 값 이상인 가장 작은 키" 같은 질의를
지원합니다. 무엇이 필요한지에 따라 고릅니다.

2. 집합으로 중복 제거하기

set<int> s;
for (int i = 0; i < n; i++) { int x; cin >> x; s.insert(x); }
cout << s.size() << '\n';   // 서로 다른 값의 개수

nums = set()
for _ in range(n):
    nums.add(int(input()))
print(len(nums))            # 서로 다른 값의 개수

insert/add는 이미 있는 값을 다시 넣어도 무시되므로, 자연스럽게 중복이
제거됩니다.

3. 맵으로 개수 세기

가장 흔한 활용입니다. "각 단어가 몇 번 등장했는가?"

map<string, int> cnt;
cnt[word]++;     // 없으면 0에서 시작해 1 증가

from collections import Counter
cnt = Counter(words)        # 한 줄로 빈도 집계
print(cnt["apple"])

C++에서 cnt[word]++는 키가 없으면 자동으로 0을 만든 뒤 증가시킵니다.
이 동작 때문에 "단순히 조회만 했는데 키가 생겨 버리는" 부작용을 주의해야 합니다.

4. 복잡도 감각

\(N\)개의 값을 모두 넣고 모두 조회한다면

• 해시 기반: 평균 \(O(N)\)
• 트리 기반: \(O(N \log N)\)

둘 다 배열을 매번 훑는 \(O(N^2)\)보다 압도적으로 빠릅니다. "검색·중복 제거·빈도
집계가 반복되면 집합/맵"이라는 반사신경을 기르세요.

5. 해시의 최악 경우

unordered_map은 평균 \(O(1)\)이지만, 악의적으로 설계된 입력에서는 해시 충돌로
\(O(N)\)까지 느려질 수 있습니다(해시 충돌 공격). 안정성이 중요하면 트리 기반
map을 쓰거나 커스텀 해시를 적용합니다. 파이썬 dict도 정수/문자열 키에서
실용적으로 매우 빠르지만 같은 원리를 따릅니다.

정리

"있나 없나"는 집합, "몇 개·무엇과 짝"은 맵. 정렬된 순서가 필요하면 트리 기반,
순수 속도만 필요하면 해시 기반을 고르세요. 다음 강의에서 실제 API를 다룹니다.

라이브러리를 손에 익히기

집합과 맵의 효과는 라이브러리 API를 정확히 아는 데서 나옵니다. C++의 STL과
파이썬의 자료형을 나란히 정리합니다.

1. 집합 핵심 연산

set<int> s;
s.insert(5);                 // 삽입
s.erase(5);                  // 삭제 (없어도 에러 아님)
if (s.count(5)) { /* 있음 */ }   // 존재 확인
auto it = s.find(5);         // 반복자 (없으면 s.end())
cout << s.size();            // 크기

s = set()
s.add(5)
s.discard(5)                 # 없어도 에러 없음 (remove는 에러)
if 5 in s: pass              # 존재 확인 — 평균 O(1)
print(len(s))

집합 연산도 유용합니다.

a, b = {1, 2, 3}, {2, 3, 4}
print(a & b)   # 교집합 {2, 3}
print(a | b)   # 합집합 {1, 2, 3, 4}
print(a - b)   # 차집합 {1}

2. 맵 핵심 연산

map<string, int> m;
m["a"] = 10;                 // 대입
m["b"]++;                    // 없으면 0에서 시작
if (m.count("a")) ...        // 존재 확인 (조회 부작용 없음)
m.erase("a");
for (auto& [k, v] : m)       // 키 정렬 순서로 순회
    cout << k << ' ' << v << '\n';

d = {}
d["a"] = 10
d["b"] = d.get("b", 0) + 1   # 없으면 0
if "a" in d: ...
del d["a"]
for k, v in d.items():
    print(k, v)

m.count(key)로 먼저 확인하는 습관을 들이면 C++에서 m[key]가 키를 만들어
버리는 함정을 피할 수 있습니다.

3. 정렬된 맵/집합의 무기: lower_bound

트리 기반 set/map은 "이 값 이상인 첫 원소"를 \(O(\log N)\)에 찾습니다.

set<int> s = {1, 3, 5, 7};
auto it = s.lower_bound(4);   // 4 이상 첫 원소 → 5
if (it != s.end()) cout << *it;   // 5

"내 키보다 큰 가장 가까운 값" 같은 질의는 이 기능 하나로 풀립니다. 파이썬에는
정렬 집합이 기본 제공되지 않아, 필요하면 bisect로 정렬 리스트를 관리하거나
sortedcontainers 같은 외부 모듈을 씁니다.

4. multiset / Counter

같은 값을 여러 개 담아야 하면 C++은 multiset, 파이썬은 Counter를 씁니다.

multiset<int> ms;
ms.insert(5); ms.insert(5);
ms.erase(ms.find(5));        // 주의: erase(5)는 5를 전부 지운다!

multiset::erase(값)은 그 값을 가진 원소를 모두 지웁니다. 하나만 지우려면
반드시 erase(find(값))을 쓰세요. 이것이 가장 흔한 실수입니다.

5. 흔한 실수 정리

• C++ m[key]의 키 생성 — 조회만 할 땐 count나 find를 쓰자.
• unordered_map 순서 기대 — 해시 맵은 순서가 없다. 정렬 순회가 필요하면 map.
• multiset::erase(값)로 전부 삭제 — 하나만 지우려면 find로 위치를 지정.
• 파이썬 set.remove — 없는 값을 지우면 예외. 안전하게는 discard.

6. 패턴 알아보기

• "서로 다른 ~의 개수" → 집합 크기.
• "각 ~가 몇 번" / "~와 짝지어" → 맵.
• "내 값보다 큰 가장 가까운 값" → 정렬 집합 + lower_bound.

검색·집계가 병목이면 거의 항상 집합/맵이 답입니다.

실전에서 집합·맵 문제 알아보기

집합과 맵은 단독 출제보다 "이걸 떠올리면 풀이가 한 줄로 줄어드는" 보조
도구로 훨씬 자주 등장합니다. 그 순간을 포착하는 법을 정리합니다.

1. 출제 신호

• "~가 존재하는가?", "이전에 나온 적이 있는가?" — 존재 판정은 집합의
  \(O(1)\)/\(O(\log N)\) 검색이 정답입니다.
• "몇 종류인가?" — 전부 집합에 넣고 크기를 보면 끝.
• "각 ~가 몇 번 등장하는가?" — 값 → 횟수 맵(카운터).
• 두 수의 합이 \(X\)인 쌍 — \(a\)를 보며 \(X - a\)가 집합에 있는지 확인하면
  \(O(N^2)\)이 \(O(N)\)으로 줄어듭니다.
• 키가 문자열·좌표 쌍처럼 배열 인덱스로 못 쓰는 모양이다 — 맵이 필요합니다.

2. 풀이 결정 절차

1. 순서/정렬이 필요한가? — "가장 가까운 값", "범위 검색"이 필요하면
   정렬 맵(C++ map/set), 존재·횟수만 필요하면 해시(unordered_map,
   파이썬 dict/set)가 더 빠릅니다.
2. 중복을 허용해야 하는가? — 같은 값을 여러 개 보관하려면 multiset
   또는 값 → 개수 맵.
3. 키 타입을 정합니다 — 좌표 쌍이면 pair/튜플, 문자열이면 그대로.
4. 연산 횟수 × \(O(\log N)\)이 제한 안인지 확인합니다.

3. 자주 하는 실수

• C++ map의 [] 조회가 원소를 만든다. 존재 확인을 m[key]로 하면
  없던 키가 0으로 삽입됩니다. 크기가 변하고 순회 결과가 달라집니다.

// 나쁨: if (m[key] > 0) ...      ← 없던 key가 삽입됨
if (m.count(key)) { ... }          // 또는 m.find(key) != m.end()

• multiset에서 값으로 erase. ms.erase(5)는 5를 전부 지웁니다.
  하나만 지우려면 ms.erase(ms.find(5)).
• 순회 중 삭제. C++에서 erase는 반복자를 무효화합니다.
  it = ms.erase(it); 패턴을 쓰세요. 파이썬도 순회 중인 dict/set을
  수정하면 RuntimeError입니다.
• 해시 컨테이너 과신. unordered_map은 저격 입력에서 \(O(N)\)으로
  느려질 수 있습니다. 시간이 빡빡하면 정렬 맵이나 커스텀 해시를 고려하세요.
• 파이썬 KeyError. 카운터는 d[k] = d.get(k, 0) + 1 또는
  collections.Counter로.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 것부터 어려운 것 순입니다. 앞쪽은
존재 판정·종류 세기, 뒤쪽은 카운터와 multiset이 필요한 문제로 이어집니다.

각 문제에서 "키는 무엇이고, 값은 무엇이고, 순서가 필요한가"를 먼저 적는
습관을 들이세요. 3문제 이상 풀어 클리어하면 레이팅의 CLASS 보너스에
반영됩니다. 집합·맵은 이후 거의 모든 문제에서 보조 도구로 쓰입니다.