[백준/C++] 1764번 듣보잡
2021. 2. 9. 00:45ㆍ알고리즘/이분 탐색
728x90
반응형
문제: www.acmicpc.net/problem/1764
1764번: 듣보잡
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다.
www.acmicpc.net
문제풀이
이분 탐색 문제이다.
벡터 3개를 선언하여
하나는 듣도 못한 사람, 하나는 보도 못한 사람, 하나는 둘의 중복되는 문자열인 듣도보도 못한 사람을 넣는다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int N, M;
cin>>N>>M;
vector<string> v1; //듣도 못한 사람
vector<string> v2; //보도 못한 사람
vector<string> v3; //듣보잡
string str;
for(int i=0; i<N; i++){
cin>>str;
v1.push_back(str);
}
for(int i=0; i<M; i++){
cin>>str;
v2.push_back(str);
}
sort(v1.begin(), v1.end()); //이분 탐색을 위해 듣도 못한 사람을 정렬해준다.
for(int i=0; i<v2.size(); i++){ //중복되는지 이분 탐색을 통하여 검사
int start = 0;
int end = v1.size()-1;
while(start<=end){
int mid = (start+end)/2;
if(v1[mid] == v2[i]){
v3.push_back(v1[mid]);
break;
}
else if(v1[mid].compare(v2[i]) < 0){
start = mid + 1;
}
else{
end = mid - 1;
}
}
}
sort(v3.begin(), v3.end()); //듣보잡 정렬
cout<<v3.size()<<"\n";
for(int i=0; i<v3.size(); i++)
cout<<v3[i]<<"\n";
return 0;
}
결과
728x90
반응형
'알고리즘 > 이분 탐색' 카테고리의 다른 글
[백준/C++] 1620번 나는야 포켓몬 마스터 이다솜 (0) | 2021.02.06 |
---|---|
[백준/C++] 1920번 수 찾기 (0) | 2021.02.01 |
[백준/C++] 2805번 나무 자르기 (0) | 2021.01.29 |