[BOJ 14425번] (Hash) 문자열 집합 (C++)

문자열 집합 (실버 III)

문제

전체 문제 보기

14425번: 문자열 집합

접근법

해당 문제는 집합 S에 포함될 N개의 문자열들을 모두 해시 테이블에 저장한 뒤, 그 뒤에 주어지는 M개의 문자열을 해시 테이블에 탐색하여 해결하는 간단한 문제이다. (중복되는 문자열은 없다.)

 

해시 테이블에 삽입 및 탐색을 하는 시간 복잡도는 \(O(1)\)이기 때문에 전체 시간 복잡도는 \(O(n)\)이며 공간 복잡는 문자열 개수만큼 공간이 필요하기 때문에 마찬가지로 \(O(n)\)이다.

구현

#include <unordered_set>
#include <string>
#include <iostream>

// 입출력 성능 향상을 위한 설정
#define endl '\n'

using namespace std;

int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N; // 집합 S의 문자열 개수
    int M; // 검사할 문자열 개수
    cin >> N >> M;

    int answer{ 0 };
    unordered_set<string> ht;
    while (N--)
    {
        string str;
        cin >> str;
        ht.emplace(str);
    }

    while (M--)
    {
        string str;
        cin >> str;
        if (ht.find(str) != ht.end())
        {
            answer++;
        }
    }

    cout << answer;

    return 0;
}