문제풀이/백준
[C++] 백준 1764번 문제풀이
Viper1
2021. 2. 11. 19:48
이 문제를 풀 때 들었던 생각은
듣도 못한 사람을 vector 에 넣고
보도 못한 사람이 듣도 못한 사람의 vector 안에 있다면 듣보잡의 vector안에 넣어야 겠다고 생각했다.
보도 못한 사람이 듣도 못한 사람의 vector 안에 있는가를 알기 위해선
탐색을 해야하는데 시간이 많이 걸리기 때문에
binary search 를 이용하여 풀었다.
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<string>db;
vector<string>dbj;
while (N--) {
string name;
cin >> name;
db.push_back(name);
}
sort(db.begin(), db.end());
while (M--) {
string name;
cin >> name;
if (binary_search(db.begin(), db.end(), name)) {
dbj.push_back(name);
}
}
sort(dbj.begin(), dbj.end());
cout << dbj.size() << "\n";
for (auto x : dbj)
cout << x << "\n";
return 0;
}