C++ STL unordered_map 완전 정리 — 코딩테스트 실전편

코딩테스트 준비 #1

C++ unordered_map 완전 정리 — 해시맵 기초부터 실전까지

STL · unordered_map · 해시맵 · 프로그래머스 · 완주하지 못한 선수

🎯 목표

코딩테스트 해시맵 유형을 C++로 풀기 위해 unordered_map 기본 문법을 정리하고, 프로그래머스 완주하지 못한 선수(Level 1) 문제에 직접 적용한다.

📌 map vs unordered_map

항목	map	unordered_map
내부 구조	레드블랙트리	해시테이블
탐색 시간복잡도	O(log N)	평균 O(1)
키 정렬	자동 정렬됨	순서 없음
코테 기본 선택	❌	✅

코딩테스트에서는 거의 항상 unordered_map을 써라. 키 정렬이 필요한 경우에만 map을 쓴다.

🔧 기본 문법 — 핵심 4가지

1. 추가 / 증가

// 없으면 0 생성 후 +1, 있으면 +1
counter["kim"]++;
// 직접 대입 (있으면 덮어씀)
counter["kim"] = 5;

2. 존재 여부 확인 vs 값 접근

// count() → 키 존재 여부만 반환 (0 또는 1)
if (counter.count("kim") > 0) { }

// [] 연산자 → 값(int) 반환
int val = counter["kim"];

⚠️ count()는 값을 반환하는 게 아니다. 키가 있냐 없냐만 알려준다.

3. 삭제

counter.erase("kim"); // 키:값 쌍 자체가 사라짐

4. 순회

// map의 원소 자체가 pair<string, int>다
for (auto& [key, value] : counter) // C++17 구조적 바인딩
{
  // key = 키(string), value = 값(int)
}

⚡ insert vs [ ] 연산자 차이

방법	키가 이미 있을 때	코테 사용 빈도
insert()	무시됨 (기존 값 유지)	낮음
[] 연산자	덮어씀	높음 ✅

🔥 실전 적용 — 완주하지 못한 선수

마라톤 전체 참가자와 완주자 명단이 주어질 때, 완주하지 못한 선수 1명을 찾아라. 동명이인 있음.

완전탐색 → O(N²) → 시간초과

// find()로 하나씩 검색 → O(N) × N번 = O(N²)
// N=100,000이면 100억 번 연산 → 시간초과

unordered_map → O(N) → 통과

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion)
{
  string answer = "";
  unordered_map<string, int> counter;

  // 1. 전체 참가자 횟수 저장
  for (auto& part : participant)
    counter[part]++;

  // 2. 완주자 횟수 차감
  for (auto& comp : completion)
    counter[comp]--;

  // 3. 횟수가 남은 사람 = 완주 못한 선수
  for (auto& [key, value] : counter)
  {
    if (value > 0)
    {
      answer = key;
      break;
    }
  }
  return answer;
}

동명이인 처리가 자동으로 되는 이유: 이름이 아닌 횟수로 추적하기 때문이다. "kim"이 참가자에 2명, 완주자에 1명 있으면 counter["kim"] = 1로 남는다.

💡 배운 것

상황	코드
값 추가/증가	counter[key]++
값 감소	counter[key]--
존재 여부	counter.count(key) > 0
값 접근	counter[key]
순회	for (auto& [key, value] : counter)
삭제	counter.erase(key)

다음 포스팅: unordered_set으로 중복 제거하기 — 프로그래머스 폰켓몬