백준 1764번 c++ 풀이

안녕하세요 오늘은 이진탐색으로 문제를 풀어보겠습니다.

 

전략:

1. see(보지 못한 사람), hear(듣지 못한 사람), result 라는 이름의 string 타입의 vector를 선언여 see와 hear를 구분하여 input을 받는다.

2. see를 탐색할 예정이기 때문에 see를 sort해준다. 어느 이진탐색과 탐색을 실행하고, hear[i]와 see[mid]가 같으면 그 값을 result 뒤에 넣어준다. 

3. 최종적으로 result의 길이를 출력하고, sort하여 사전순으로 출력한다.

 

코드:

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, M;
	cin>>N>>M;
	vector<string> see(N);
	vector<string> hear(M);
	vector<string> result;
	for(int i= 0; i<N; ++i){
		string x;
		cin>>x;
		see[i] = x;
	}
	for(int i= 0; i<M; ++i){
		string x;
		cin>>x;
		hear[i] = x;
	}
	sort(see.begin(), see.end()); //see를 탐색할 예정
	for(int i  = 0; i<M; ++i){
		int low  = 0, high = N-1;
		while(high>=low){
			int mid = (low + high)/2;
			if(hear[i] == see[mid]){
				result.emplace_back(hear[i]);
				break;

			}
			else if(hear[i]>see[mid]){
				low = mid+1;
			}
			else{
				high=  mid-1;
			}
		}
	}
	cout<<result.size()<<"\n";
	sort(result.begin(), result.end());
	for(int i= 0 ;i<result.size(); ++i){
		cout<<result[i]<<"\n";
	}
}