[백준 1764] 알고리즘 60일차 : 듣보잡

www.acmicpc.net/problem/1764

1764번: 듣보잡

C++ 이분탐색

모닝 코딩이네요

또 쉽게가려고 이분탐색 들여다보고있는데 제목이 재밌어서요..(핑계)

근데 문제가 더 재밌네요 듣도 못한 사람과 보도 못한 사람들이 주어지고 듣도 보도 못한 사람을 구하는거라니..ㅋㅋ

문자열 벡터 이분탐색 정렬 썼습니다.

 

접근방법

듣도 못한 사람 명단 벡터에 저장 후 사전순으로 정렬

보도 못한 사람을 듣도 못한 사람들에서 이분탐색으로 찾고 듣도보도못한 사람 명단에 push

듣도보도못한 사람 명단 사전순 정렬 출력 끝

 

소스코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> hearSee;
vector<string> hear;
int H, S;
void binarySearch(string see){
    int s = 0;
    int e = H-1;
    int mid;
    while(s <= e){
        mid = (s+e)/2;
        if(hear[mid].compare(see) == 0){
            hearSee.push_back(see);
            return;
        }else if(hear[mid].compare(see) > 0){
            e = mid-1;
        }else{
            s = mid+1;
        }
    }
    return;
}
int main(){
    cin >> H >> S;
    string hearname;
    for(int i = 0 ; i < H ; i++){
        cin >> hearname;
        hear.push_back(hearname);
    }
    sort(hear.begin(), hear.end());
    string see;
    for(int i = 0 ; i < S ; i++){
        cin >> see;
        binarySearch(see);
    }
    sort(hearSee.begin(), hearSee.end());
    cout << hearSee.size() << "\n";
    for(int i = 0 ; i < hearSee.size() ; i++){
        cout << hearSee[i] << "\n";
    }
    return 0;
}