백준 17219 c++ 풀이

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

 

전략:

1. string, string 을 페어로 하는 pair를 타입으로 하는 v라는 vecotr를 만들고, string 타입으로 x, y를 입력 받아서 각각 v[i].first, v[i].second에 대입해주고 이진탐색을 위해 sort를 해준다.

2. string 타입의 x라는 변수를 입력받고, 이진탐색을 진행하여 만약 x와 v[mid].first가 같으면 v[mid].second를 출력한다.

 

코드:

#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<pair<string, string>> v(N);
	for(int i= 0; i<N; ++i){
		string x, y;
		cin>>x>>y;
		v[i].first = x;
		v[i].second = y;
	}
	sort(v.begin(), v.end());
	for(int i= 0; i<M; ++i){
		string x;
		cin>>x;
		int high = N-1, low=  0;
		while(1){
			int mid = (high + low)/2;
			if(x==v[mid].first){
				cout<<v[mid].second<<"\n";
				break;
			}
			else if(x<v[mid].first){
				high = mid-1;
			}
			else{
				low = mid+1;
			}
			
		}
	}
}