[백준 1764] 듣보잡

듣보잡

문제 설명

문제 설명은 사진과 같다.

---

알고리즘

1. N,M을 입력받고 이름까지 입력 받는다
2. 이분탐색을 이용하기 위해 sort 함수로 정렬한다
3. 이분 탐색을 해서 중복 된 값을 찾아낸다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;

int N, M;
int main()
{        
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    vector <string>v;//듣도 못한 사람
    vector <string> vs;//보도 못한 사람
    cin >> N >> M;

    for (int i = 0; i < N; i++)//듣도 못한 사람 입력
    {
        string s;
        cin >> s;
        v.push_back(s);
    }
    for (int i = 0; i < M; i++)//보도 못한 사람 입력
    {
        string s;
        cin >> s;
        vs.push_back(s);
    }
    sort(v.begin(), v.end());//정렬
    sort(vs.begin(), vs.end());
    vector <string> ans;
    for (int i = 0; i < N;i++)//시간을 줄이기 위한 이분 탐색 비교
    {
        string temp = v[i];
        int left = 0;
        int right = M - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (vs[mid] == temp)
            {
                ans.push_back(temp);
                break;
            }
            else if (vs[mid] > temp)
                right = mid - 1;
            else
                left = mid + 1;
        }
    }
    cout << ans.size() << "\n";//답 갯수 출력
    for (int i = 0; i < ans.size(); i++)//답 출력 
        cout << ans[i] << "\n";

    return 0;
}

고찰

이번 문제는 단순히 문자열을 입력 받고 중복 된 값이 있는지 확인하여 그 수와 내용을 출력하면 되는 문제였다. 이분 탐색을 사용하여 간단하게 만들 수 있었다.
검색을 해보니까 직접 이진 탐색을 구현할 수 도 있고 algorithm 헤더에 있는 binary_search함수를 사용해도 된다.