백준 1764번 듣보잡

문제 링크입니다: https://www.acmicpc.net/problem/1764

정렬된 듣도 못한 사람의 리스트를 탐색할 때 시간 복잡도가 O(N)인 find 함수를 사용하면 TLE가 발생하는 문제였습니다.

따라서 이진 탐색(binary search) 함수를 직접 구현하여 듣도 못하고 보도 못한 사람을 result 벡터에 추가했습니다,

주의할 점은, 이진 탐색을 하기 때문에 v 벡터도 정렬해야하고 사전 순서대로 출력해야하기 때문에 result 벡터도 정렬해야한다는 점입니다!

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

 

int N, M;

vector<string> v; //듣도 못한 사람의 리스트

 

//이진 탐색

bool binarySearch(int low, int high, string name)

{

        if (low > high)

                 return false;

        else

        {

                 int mid = (low + high) / 2;

 

                 if (!v[mid].compare(name))

                         return true;

                 else if (v[mid] > name)

                         return binarySearch(low, mid - 1, name);

                 else

                         return binarySearch(mid + 1, high, name);

        }

}

 

int main(void)

{

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

        {

                 string name;

                 cin >> name;

 

                 v.push_back(name);

        }

 

        sort(v.begin(), v.end());

 

        vector<string> result;

        for (int i = 0; i < M; i++)

        {

                 string name;

                 cin >> name;

 

                 //듣도 못하고 보도 못한 사람

                 if (binarySearch(0, v.size() - 1, name))

                         result.push_back(name);

        }

 

        sort(result.begin(), result.end());

 

        cout << result.size() << endl;

        for (int i = 0; i < result.size(); i++)

                 cout << result[i] << endl;

 

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~