백준-집합과 맵 14425 문자열 집합

문자열 집합

집합 S에 포함되는 문자열이 몇 개인지 구하는 프로그램

메모리를 상당히 많이 줬으므로 길이 기반, 첫 문자 기반 해시 버킷 분할 가능

최대 메모리 사용량은 20000 * 500byte * 26(char)

제약사항

• 0 < N <= 10,000
• 0 < M <= 10,000
• 0 < strLen <= 500

주의 사항

없다.

CPP풀이

문자열 집합_14425.cpp

/**
 * 백준 문자열 집합_14425
 * 
 * 
 * 제한사항
 *****************************************
 * 
 *****************************************
 *
 *
 *
 * 주의
 * 없다.
 * 
 * 풀이시간 30분
 */


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;

    vector<string> strArr[501][26];
    bool isSorted[501][26] = { 0 };

    cin >> N >> M;
    for (int i = 0; i < N; ++i)
    {
        string str;
        cin >> str;

        int strlen = str.length();
        char ch = str.front();
        int headIDX = ch - 'a';
        strArr[strlen][headIDX].push_back(str);
    }
  
    int count = 0;

    for (int i = 0; i < M; ++i)
    {
        string str;
        cin >> str;

        int strlen = str.length();
        char ch = str.front();
        int headIDX = ch - 'a';
        
        if (!isSorted[strlen][headIDX])
        {
            sort(strArr[strlen][headIDX].begin(), strArr[strlen][headIDX].end());
            isSorted[strlen][headIDX] = true;
        }

        if (binary_search(strArr[strlen][headIDX].begin(), strArr[strlen][headIDX].end(), str))
        {
            count++;
        }
    }

    cout << count << '\n';
    return 0;
}

모든 예제 코드의 소스파일은 제 개인 깃허브 레포지토리 에 있습니다.

Workspace/알고리듬 풀이 at main · cyphen156/Workspace · GitHub

Workspace/알고리듬 풀이 at main · cyphen156/Workspace