[백준 17219][이분탐색][C++] 비밀번호 찾기

 

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

17219번: 비밀번호 찾기

 

사이트 주소와 비밀번호를 페어로 묶은 벡터를 정렬하여, 이분탐색으로 사이트 주소의 위치번호를 찾아내면 쉽게 풀 수 있는 문제이다.

이분탐색이란, 정렬된 배열에서 중간을 기준으로 찾는 값이 더 작으면 앞쪽, 크면 뒤쪽을 보는 것을 반복하며 찾는 방법이다.

 

입력받고, 정렬한 배열이 위와 같고, 우리는 nate.com의 비밀번호를 찾고 있다고 가정해보자.

맨 처음 탐색은 0~6이 될 것이다.

 

기준점이 되는 중앙은 (0+6)/2, 3번 자리인 naver.com이다. 아스키코드 상 nate.com은 naver.com보다 더 작다. (n==n, a==a, t<v)

그러므로 다음 탐색 위치는 0~3이 된다.

 

기준점이 되는 중앙은 (0+3)/2, 1번 자리인 daum.net이다. 아스키코드 상 nate.com은 daum.net보다 크다. (n>d)

그러므로, 다음 탐색 위치는 2~3이 된다.

 

기준점이 되는 중앙은 (2+3)/2, 2번 자리인 nate.com이다. 찾는 값과 같으므로 위치번호를 반환해준다.

 

이렇게 찾은 사이트 주소의 위치번호에 해당하는 비밀번호를 출력해준다.

 

이 문제에서는 비밀번호를 찾으려는 사이트 주소는 배열에 있는 주소만 주어지므로 못 찾는 경우는 고려하지 않아도 된다.

 

 

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

int n,m; string input1, input2;
vector <pair<string, string> > list;

int search(int l, int r, string a){
    int mid = (l+r)/2; // 기준점을 중앙으로 잡는다.
    if(list[mid].first==a) return mid; // 기준점과 찾는 주소가 같으면 기준점을 반환해준다.
    
    return list[mid].first>=a ? search(l,mid,a) : search(mid+1,r,a);
    // 배열의 기준점에 해당하는 주소보다 작으면 앞쪽, 크면 뒤쪽을 찾는다.
}

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>input1>>input2;
        list.push_back({input1,input2}); // 주소와 비밀번호를 pair로 묶어 벡터에 넣어준다.
    }
    sort(list.begin(),list.end()); // 배열을 오름차순으로 정렬해준다.
    
    for(int i=0; i<m; i++){
        cin>>input1;
        int x = search(0,n-1,input1);
        cout<<list[x].second<<'\n';
    }
}