[토요라운드] D. 문자열 집합 (14425)

ㅂㄷㅂㄷㅂㄷ 시간초과 났는데 해결을 못했다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#pragma warning(disable:4996)
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int n, m;
    cin >> n >> m;
    
    vector<string> s1(n);
    for (int i = 0; i < n; i++)
        cin >> s1[i];
        
    vector<string> s2(m);
    for (int i = 0; i < m; i++)
        cin >> s2[i];
    
    int ans = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (s2[i] == s1[j])
            {
                ans++;
            }
        }
        
    }
    
    cout << ans << "\n";
    
    return 0;
}

 

구현은 위처럼 했다

 

짜면서 이렇게 하면 시간초과 날텐데...! 날텐데...! 싶었는데 정말로 시간초과 났다.

 

m 집합을 n번 확인하는데 확인하는 부분이 문자열 길이만큼 일테니 시간초과가 날 수 밖에 없지....

 

---

헉 대박 map을 쓰면 된다!!

 

map을 쓰면 값을 찾는데 log n이 걸릴 것이므로 m log n 시간이 걸릴 것이다. 

 

와.... 시간초과가 나면 이렇게 다른 자료구조를 써서 해결가능하구나

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#pragma warning(disable:4996)
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int n, m;
    cin >> n >> m;
    
    
    map<string, bool> mp;
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        mp[str] = true;
    }
        
    int cnt = 0;
    for (int i = 0; i < m; i++)
    {
        string str;
        cin >> str;
        
        if (mp[str])
            cnt++;
    }
    
    cout << cnt << "\n";
    
    return 0;
}