이 문제를 풀 때 들었던 생각은
듣도 못한 사람을 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;
}
'문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 1927번 문제풀이 (0) | 2021.02.15 |
---|---|
[C++] 백준 1389번 문제풀이 (0) | 2021.02.14 |
[C++] 백준 1697번 문제풀이 (0) | 2021.02.11 |
[C++] 백준 1620번 문제풀이 (0) | 2021.02.11 |
[C++] 백준 1463번 문제풀이 (0) | 2021.02.09 |