[백준] 1764 듣보잡

 

백준 10815번 문제의 문자열버전이다. 풀이가 비슷하므로 아래 문제풀이를 참고해도 될거같다.

https://everydayyy.tistory.com/44

[백준] 10815 숫자카드

 

 

이진탐색으로 해당문자열이 있는지 탐색하고, 있다면 answer 벡터에 저장해서, 마지막에 정렬하여 출력하면 끝!!

숫자에 이어서 영문자열의 경우 또한 STL의 std::sort()함수로 처리가 가능하다는 것을 보여준 문제같다.

 

void sort(T start, T end, Compare comp);

sort의 parameter에서 compare부분을 따로 만들어주면 사용자가 정의한 함수대로 정렬이 이루어지는데, 

생략하고 sort(v.begin(),v.end())와 같이 시작,끝점만 적는다면 default로 오름창순정렬을 해준다.

 

따라서 이번문제와 같이 단순히 사전순정렬만 요구할 경우에는 사용자정의함수를 따로 만들 필요 없이 해결 가능하다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int n, m;
vector<string> v;
vector<string> answer;
 
void BSearch(string target)
{
    int low = 0;
    int high = v.size() - 1;
    int mid;
 
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (target == v[mid])
        {
            answer.push_back(v[mid]);
            return;
        }
        else if (target > v[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    return;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    
    cin >> n >> m;
 
    v.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
 
    sort(v.begin(),v.end());
 
    for (int i = 0; i < m; i++)
    {
        string str;
        cin >> str;
        BSearch(str);    
    }
 
    sort(answer.begin(), answer.end());
 
    cout << answer.size() << "\n";
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i] << "\n";
    }
 
 
    return 0;
}