[백준/C++] 1764번 듣보잡

문제: www.acmicpc.net/problem/1764

1764번: 듣보잡

 

 

문제풀이

 

이분 탐색 문제이다.

 

벡터 3개를 선언하여

하나는 듣도 못한 사람, 하나는 보도 못한 사람, 하나는 둘의 중복되는 문자열인 듣도보도 못한 사람을 넣는다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N, M;
    cin>>N>>M;

    vector<string> v1; //듣도 못한 사람
    vector<string> v2; //보도 못한 사람
    vector<string> v3; //듣보잡

    string str;
    for(int i=0; i<N; i++){
        cin>>str;
        v1.push_back(str);
    }

    for(int i=0; i<M; i++){
        cin>>str;
        v2.push_back(str);
    }

    sort(v1.begin(), v1.end()); //이분 탐색을 위해 듣도 못한 사람을 정렬해준다.

    for(int i=0; i<v2.size(); i++){ //중복되는지 이분 탐색을 통하여 검사
        int start = 0;
        int end = v1.size()-1;

        while(start<=end){
            int mid = (start+end)/2;

            if(v1[mid] == v2[i]){
                v3.push_back(v1[mid]);
                break;
            }
            else if(v1[mid].compare(v2[i]) < 0){
                start = mid + 1;
            }
            else{
                end = mid - 1;
            }
        }
    }

    sort(v3.begin(), v3.end()); //듣보잡 정렬

    cout<<v3.size()<<"\n";

    for(int i=0; i<v3.size(); i++)
        cout<<v3[i]<<"\n";

    return 0;
}

 

 

결과