[백준] 문자열 집합 14425 (Silver4) - C++ Hash 함수

https://www.acmicpc.net/problem/14425

문제 간단 요약

• 문자열로 이루어진 집합 S가 주어진다.
• 이후 주어지는 문자열들 중
  집합 S에 포함된 문자열의 개수를 구하는 문제다.
• 핵심 연산은 반복적인 문자열 존재 여부 확인이다.

-> 문자열 비교가 많이 발생하므로,
빠른 탐색이 가능한 자료구조를 선택하는 것이 중요하다.

---

문제 접근 아이디어

이 문제를 단순하게 풀면 다음과 같다.

• 문자열을 하나씩 저장
• 이후 문자열이 있는지 매번 비교 (==)로 확인

하지만 문자열 비교는 길이에 따라 비용이 커지고,
전체 시간복잡도는 비효율적으로 커질 수 있다.

여기서 관점을 바꾸면 문제는 이렇게 변한다.

“이 문자열이 집합에 있는지 없는지만 빠르게 확인하자”

 

이럴 때 가장 적합한 자료구조가 해시(Hash) 이다.

---

해결 방법: unordered_set<string>

C++에서는 unordered_ 계열 컨테이너에
문자열 해시 함수가 이미 내장되어 있다.

• 문자열을 그대로 넣으면 자동으로 해싱
• 평균 시간복잡도: O(1)

따라서 이 문제는
unordered_set<string> 하나로 해결 가능하다.

---

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

    unordered_set<string> Strings; // 내장 hash 사용

    for(int i = 0; i < n; i++){
        string str;
        cin >> str;
        Strings.insert(str);
    }

    int res = 0;
    for(int i = 0; i < m; i++){
        string str;
        cin >> str;
        if(Strings.find(str) != Strings.end()){
            res++;
        }
    }

    cout << res;
    return 0;
}

---

코드 핵심 설명

• unordered_set<string> Strings
  • 문자열을 키로 사용하는 해시 기반 집합
  • 내부적으로 std::hash<string> 사용
• Strings.insert(str)
  • 문자열을 해시 테이블에 저장
• Strings.find(str)
  • 문자열이 존재하면 iterator 반환!! (주의)
  • 없으면 Strings.end()

-> 문자열 존재 여부 확인이 평균 O(1) 이다.

C++의 해시: 우리가 직접 만들 필요가 없는 이유

이번 문제를 풀면서 새로 알게 된 점은 이것이었다.

C++에서는 굳이 해시 함수를 직접 구현할 필요가 없다.

이유 1. 충돌 처리

• 직접 구현 → 충돌 발생 시 처리 로직 필요
• unordered_set → STL이 내부적으로 처리

이유 2. 성능과 안정성

• STL 해시는 다양한 문자열 패턴에서도
  값이 고르게 분산되도록 설계되어 있다.

시간복잡도 분석

• 문자열 삽입: O(N)
• 문자열 탐색: O(M)
• 전체 시간복잡도: O(N + M)

👉 문자열 길이가 길어져도
이중 반복문보다 훨씬 안정적이다.