SW Expert Academy 2948. 문자열 교집합[C++]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV-Un3G64SUDFAXr&categoryId=AV-Un3G64SUDFAXr&categoryType=CODE&problemTitle=2948&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

 

#문제 간단 정리

해쉬문제다

 

#문제 해결 방법

unordered map 으로 풀 수 있지만..

해쉬를 잘 알아볼겸 해쉬를 직접 구현한 코드로 올린

 

#전체 코드

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

const int TABLE_SIZE = 100003; // 적당한 소수 크기의 해시 테이블

// 간단한 문자열 해시 함수 (131을 곱하는 방식)
int getHash(const string& s) {
    unsigned long long hash_val = 0;
    for (char c : s) {
        hash_val = hash_val * 131 + c;
    }
    return hash_val % TABLE_SIZE;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int N, M;
        cin >> N >> M;

        // 해시 테이블 초기화: TABLE_SIZE 크기의 벡터 배열
        vector<vector<string>> hashTable(TABLE_SIZE);

        string str;
        // 첫 번째 집합의 문자열들을 해시 테이블에 저장
        for (int i = 0; i < N; i++) {
            cin >> str;
            int idx = getHash(str);
            hashTable[idx].push_back(str);
        }

        int answer = 0;
        // 두 번째 집합의 문자열들을 하나씩 확인
        for (int i = 0; i < M; i++) {
            cin >> str;
            int idx = getHash(str);
            // 해당 해시 버킷(bucket) 내에서 문자열이 존재하는지 선형 탐색
            for (const auto& s : hashTable[idx]) {
                if (s == str) {
                    answer++;
                    break; // 중복 없이 집합에 한 번만 등장하므로 발견하면 바로 종료
                }
            }
        }

        cout << "#" << t << " " << answer << "\n";
    }

    return 0;
}