[백준/C++] 10816번: 숫자 카드 2 - unordered_map과 operator[]의 동작 원리

1. 문제 정보

• 문제 번호: 10816번
• 문제 이름: 숫자 카드 2
• 문제 요약:
• 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적힌 숫자 카드를 각각 몇 개 가지고 있는지 구하는 프로그램을 작성하라.

 

2. 접근 방법 (알고리즘)

❌ 첫 번째 시도: Vector + find_if (시간 초과)

처음에는 vector<pair<int, int>>를 만들어 {숫자, 개수}를 저장하고, 새로운 카드가 들어올 때마다 find_if로 기존에 있는 카드인지 확인했다.

• 원인: find_if는 선형 탐색(O(N)이다.
• 시간 복잡도: 카드를 입력받을 때마다 전체 벡터를 뒤지므로 O(N^2), 탐색 시에도 O(M X N)이 걸린다. N과 M이 각각 50만인 이 문제에서 이 방식은 반드시 시간 초과가 발생한다.

✅ 최종 접근: unordered_map 사용 (성공)

map을 쓰면 인덱스로 바로 접근이 가능하다!

데이터의 개수를 세거나 특정 키(Key)로 값을 즉시 찾아야 할 때는 해시 테이블(Hash Table) 기반의 unordered_map이 최적이다.

• 성능: 평균적으로 삽입과 탐색에 O(1)이 걸린다.
• 전체 복잡도: O(N + M)으로, 100만 건의 데이터도 매우 빠르게 처리할 수 있다.

 

 

3. 코드 구현 (정답)

#include <iostream>
#include <unordered_map> // 해시 테이블 기반 맵

using namespace std;

int main() {
    // 입출력 최적화
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n;
    
    // key: 카드 숫자, value: 개수
    unordered_map<int, int> myCards; 

    // 1. 카드 입력 및 카운팅
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        // operator[]를 통해 key가 없으면 0으로 초기화 후 1 증가
        myCards[num]++; 
    }

    cin >> m;
    // 2. 쿼리 수행
    for (int i = 0; i < m; i++) {
        int num;
        cin >> num;
        // key가 없으면 자동으로 0을 반환함
        cout << myCards[num] << " "; 
    }

    return 0;
}

 

---

4. 배운 점 & 회고 (TIL) ✍️

 

 

이번 문제를 풀면서 map 계열 컨테이너의 operator[]가 단순한 접근 이상의 기능을 수행한다는 점을 깊이 이해하게 되었다.

① map / unordered_map의 operator[] 동작 방식

C++의 맵 자료구조에서 myCards[num]과 같이 대괄호 연산자를 사용하면 내부적으로 다음과 같은 로직이 실행된다.

1. Key가 존재하는 경우: 해당 Key에 연결된 Value의 참조를 반환한다.
2. Key가 존재하지 않는 경우: * 새로운 원소를 맵에 자동으로 추가한다.
   • Value 타입을 "기본 초기화(Default Initialization)" 하여 반환한다.

② "기본 초기화"의 마법

Value 타입이 int일 경우, 없는 Key를 호출하면 자동으로 int()가 호출되어 0이 들어간다.

• int, double 등 숫자 타입: 0 또는 0.0으로 초기화
• string 타입: "" (빈 문자열)로 초기화
• 사용자 정의 클래스: 기본 생성자 호출

이 덕분에 if (find...) 처럼 복잡한 존재 여부 확인 로직 없이 myCards[num]++ 한 줄로 카운팅을 끝낼 수 있다. 존재하지 않던 숫자가 들어오면 0이 생기자마자 ++되어 1이 되기 때문이다.

 

③ 주의할 점

이 기능은 편리하지만, 조회만 하려고 했는데 데이터가 삽입될 수 있다는 부작용이 있다.

단순히 특정 Key가 있는지만 확인하고 싶다면 operator[] 대신 find() 함수나 count() 함수를 써야 맵의 크기가 불필요하게 커지는 것을 막을 수 있다. vector나 set 같은 다른 컨테이너는 이런 자동 삽입 기능이 없으므로 오직 맵(Map) 계열만의 특징임을 기억해야 한다.

자료구조	operator[] 특징
vector	인덱스 범위 초과 시 에러(Undefined Behavior) 발생
map	없는 Key 접근 시 기본값으로 원소 생성 후 반환
unordered_map	map과 동일 (해시 기반이라 더 빠름)

최적화된 자료구조와 언어의 특성을 잘 활용하면 코드가 훨씬 간결해지고 성능도 챙길 수 있다는 것을 다시금 느꼈다.