[c++][BOJ] 비밀번호 찾기

https://www.acmicpc.net/problem/17219

17219번: 비밀번호 찾기

저장된 사이트의 비밀번호를 찾는 문제입니다.

 

가장 먼저 pair 함수를 이용해서 사이트와 비밀번호를 저장합니다.

 

그 이후 사이트를 받아와서 저장된 벡터의 first를 비교후, 같다면 second를 출력하는 방법입니다.

 

다만, 이 방법에서 그냥 순차 검색을 이용할 경우 시간초과가 나기 때문에

 

이진검색으로 나누어서 풀었습니다. 어차피 string sort시 알파벳 순서대로 배열되기 때문이죠.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<string, string>> arr;

int binary(int start, int end, string find){
    int mid = (start + end) / 2;
    
    if(arr[mid].first == find)
        return mid;
    
    else{
        if(arr[mid].first >= find)
            return binary(start, mid, find);
        else
            return binary(mid+1, end, find);
    }
}

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    int n,m;
    cin >> n >> m;

    for(int i=0; i<n; i++)
    {
        string str1, str2;
        cin >> str1 >> str2;
        arr.push_back(pair<string, string>(str1, str2));
    }
    
    sort(arr.begin(), arr.end());
    
    for(int j=0; j<m; j++)
    {
        string str3;
        cin >> str3;
        
        int x = binary(0, n-1, str3);
        cout << arr[x].second << '\n';
    }
}