[백준 1764] 듣보잡

0. 제목

• 백준 1764 듣보잡
• BOJ 1764 듣보잡
• C++ 1764 듣보잡

---

1. 문제

https://www.acmicpc.net/problem/1764

---

2. 풀이

• string자료형을 가지고 있는 vector를 이용한다.
• binarySearch를 이용하여 탐색시간을 줄인다.
• binarySearch로 듣도 못한 사람이 들어있는 vector v를 탐색해서 보도 못한 사람과 같은 이름이 있으면 듣도 보도 못한 사람을 넣는 vector result에 push_back으로 넣어준다.
• vector result를 sort를 사용해 오름차순 정렬을 한다.
• size()를 사용해 개수를 출력하고, 원소들을 출력해준다.

---

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, M;
vector<string> v;//듣도 못한 사람
 
bool binarySearch(int low, int high, string name){
    if(low > high)
        return false;
    else{
        int mid = (low + high) / 2;
        if(v[mid] == name)
            return true;
        else if(v[mid] > name)
            return binarySearch(low, mid - 1, name);
        else
            return binarySearch(mid + 1, high, name);
    }
}
 
int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        string name;
        cin >> name;
        v.push_back(name);
    }
    
    sort(v.begin(), v.end());
    
    vector<string> result;
    for(int i = 0; i < M; i++){
        string name;
        cin >> name;
        
        //듣도 보도 못한 사람
        if(binarySearch(0, (int)v.size()-1, name))
            result.push_back(name);
    }
    
    sort(result.begin(), result.end());
    
    cout << result.size() << '\n';
    for(int i = 0; i < result.size(); i++)
        cout << result[i] << '\n';
    
    return 0;
}