백준 14425 - 문자열 집합(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

 

N개만큼 문자열이 주어지고 M개만큼 문자열이 주어질 때, M개 문자열에 N개 문자열이 몇개가 들어있는지 구하는 문제입니다.

 

N, M이 최대 10,000이기에 완전 탐색을 했다가 시간초과가 됩니다.

 

따라서 이분 탐색을 통해 N 속에 M이 들어있는지 확인해줘야 합니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>

using namespace std;

int N, M, ans;
vector<string> arr;

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        string x;
        cin >> x;
        arr.push_back(x);
    }
    sort(arr.begin(), arr.end());
    for(int i = 1; i <= M; i++){
        string x;
        cin >> x;
        if(binary_search(arr.begin(), arr.end(), x)) ans++;
    }
    cout << ans;
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요