https://www.acmicpc.net/problem/1764
1764번: 듣보잡
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다.
www.acmicpc.net
이 문제의 경우 생각 보다 쉽게 풀리는 문제일거 같았다 일단은 어차피 탐색할거라면 사전에서 이분탐색이 효율적이라 판단 되어 이분탐색으로 각각의 리스트에 중복되는게 있는 지 없는지를 판단 하려고 하였다
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string DeutBo[500000];
string Bodo[500000];
string Answer[500000];
int binarysearch(string* a, string answer, int low, int high) {
int mid;
if (low > high)
return 0;
else {
mid = (low + high) / 2;
if (answer == a[mid]) {
return 1;
}
else if (answer < a[mid])
return binarysearch(a, answer, low, mid - 1);
else
return binarysearch(a, answer, mid + 1, high);
}
}
int main() {
int N, M;
int cnt=0;
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> DeutBo[i];
}
sort(DeutBo, DeutBo+N);
for (int i = 0; i < M; i++) {
cin >> Bodo[i];
}
sort(Bodo, Bodo + M);
for (int i = 0; i < M; i++) {
if (binarysearch(DeutBo, Bodo[i], 0, M)) {
Answer[cnt] = Bodo[i];
cnt++;
}
}
cout << cnt<<'\n';
for (int i = 0; i < cnt; i++) {
cout << Answer[i] << '\n';
}
}이문제의 경우 이분탐색의 개념만 알면 풀기 쉬운 문제였다 일다 string객체는 사전적 대소관계를 비교할 수 있으므로
이분 탐색을 통해 지속적으로 비교해주면 되는 문제였다