[c++][BOJ][1764] 듣보잡

https://acmicpc.net/proble64

듣도 못한 사람과 보도 못한 사람의 입력을 받아서 둘 다 속해있는 사람을 구하는 문제입니다.

 

먼저 듣도 못한 사람의 이름을 배열에 넣고, 보도 못한 사람의 이름이 들어올 때 마다 찾아서 같은게 있다면 정답 배열에 넣고 카운트를 증가시킵니다.

 

이 때, 이진 탐색을 이용해서 시간을 줄입니다.

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

vector<string> name;
vector<string> emeqh;
int ncount = 0;

void binary(int start, int end, string find){
    int mid = (start + end) / 2;
    
    if(start > end)
        return ;
    
    if(name[mid] == find)
    {
        ncount++;
        emeqh.push_back(find);
        return ;
    }
    
    if(name[mid] > find)
    {
        return binary(start, mid-1, find);
    }
    else{
        return binary(mid+1, end, find);
    }
    
}

int main(){
    int n,m;
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        string str1;
        cin >> str1;
        name.push_back(str1);
    }
    
    sort(name.begin(), name.end());
    
    for(int j=0; j<m; j++)
    {
        string str2;
        cin >> str2;
        
        binary(0, n-1, str2);
    }
    
    cout << ncount << '\n';
    
    sort(emeqh.begin(), emeqh.end());
    for(int k=0; k<emeqh.size(); k++){
        cout << emeqh[k] << '\n';
    }
}