[백준] 1764번 : 듣보잡 - C++

문제

http://acmicpc.net/problem/1764

1764번: 듣보잡

 

---

설명

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <map>
#include <iterator>

using namespace std;

int main()
{
    int N, M;
    vector<string> hear;
    vector<string> see;
    vector<string> answer;
    cin >> N >> M;
    
    for( int i = 0;i<N;i++)
    {
        string tmp;
        cin >> tmp;
        hear.push_back(tmp);
    }
    sort(hear.begin(), hear.end());
    
    for(int i = 0;i<M;i++)
    {
        string tmp;
        cin >> tmp;
        
        if(binary_search(hear.begin(), hear.end(), tmp))answer.push_back(tmp);
    }
    sort(answer.begin(),answer.end());
    cout<<answer.size()<<endl;
    for( int i=0;i<answer.size();i++)
        cout<<answer[i]<<endl;
    
}

이 문제에서는 듣도 못한 사람 N명과 보도 못한사람 M명을 입력받는다.

듣도 못한 사람이면서 보도못한 사람, 즉 듣도 보도 못한사람을 출력해야한다.

출력 조건은 듣도 보도 못한 사람의 수를 먼저 출력하고, 사전순으로 이름을 출력하는 것이다.

 

처음에는, hear에 먼저 듣도 못한 사람을 입력 받고, 보도 못한사람을 입력 받을때마다

iterator와 find함수를 사용하였다. 하지만 이 방법은 시간초과가 나왔기 때문에 새로운 방법을 찾아야했다.

 

탐색 방법중에서 logn의 시간 복잡도를 갖는 이분 탐색이 있다.

이분탐색을 이용하기 위해서는 먼저 탐색 대상이 정렬되어 있어야한다.

따라서 hear을 사전순으로 정렬한 후, 보도 못한사람을 입력 받을때마다

binary_search함수를 사용하였다.

binary_search함수는 algorithm헤더파일의 내장함수이다.

탐색에 성공하면 true를 실패하면 false값을 반환한다.

 

binary_search(arr_begin,arr_end,find_value) 형태로 사용하면 된다.