[C++] 백준 1764 - 듣보잡

www.acmicpc.net/problem/1764

1764번: 듣보잡

<풀이>

1. 듣잡 명단과 보잡 명단을 입력받는다.

2. 듣잡 명단과 보잡 명단에 공통적으로 있는 사람을 찾고, 출력한다.

 

<해법>

1. 듣잡 명단과 보잡 명단에 공통적으로 있는 사람을 찾는 방법

=> 순차 탐색을 사용할 경우 시간초과가 발생합니다. 따라서, 이분 탐색을 이용합니다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
//입력
int n, m;
vector<string> listen;
vector<string> see;
 
//결과
vector<string> answer;
 
//듣잡 벡터에서 문자열 key 찾는 이분탐색
bool find(string key) {
 
    int start = 0, end = listen.size();
 
    while (start <= end) {
        
        int middle = (start + end) / 2;
 
        if (key < listen[middle]) {
            end = middle - 1;
        }
        else if (key > listen[middle]) {
            start = middle + 1;
        }
        //key값을 찾는 경우, true 리턴
        else {
            return true;
        }
    }
 
    //key값을 찾지 못하였을 경우, false 리턴
    return false;
}
 
int main() {
 
    //입력
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        listen.push_back(tmp);
    }
    for (int i = 0; i < m; i++) {
        string tmp;
        cin >> tmp;
        see.push_back(tmp);
    }
 
    //듣잡 벡터 사전순 정렬
    sort(listen.begin(), listen.end());
 
    for (int i = 0; i < m; i++) {
 
        //듣잡 벡터 안에 보잡 문자열이 있는지 확인
        bool isIn = find(see[i]);
 
        //듣보잡인 경우
        if (isIn) {
            //결과 벡터에 추가
            answer.push_back(see[i]);
        }
    }
 
    //결과 벡터 사전순 정렬
    sort(answer.begin(), answer.end());
    
    //결과 출력
    cout << answer.size() << "\n";
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << "\n";
    }
 
    //종료
    return 0;
}

 

이분탐색에 대해 알아볼 수 있는 문제였습니다.