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

시간 초과가 난 코드

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

int N, M;
vector<string> v;
vector<string> ans;
int main(int argc, char** argv){
  std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

  string name;
  
  cin >> N >> M;
  for(int i=0; i<N; i++){
    cin >> name;
    v.push_back(name);
  }

  for(int i=0; i<M; i++){
    cin >> name;

    for(int j=0; j<N; j++){
      if(name == v[j]){
        ans.push_back(name);
      }
    }
  }

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

  return 0;
}

for 문 2개로 탐색하였기에 O(N^2)의 시간 복잡도를 가진다.

수정한 코드

for문 2개 대신
STL 라이브러리의 정렬(퀵 소트) O(N logN)의 시간복잡도와, 이진탐색 O(log N)의 시간복잡도를 가지도록 수정하였다.

#include <iostream>
#include <vector>
#include <algorithm> // 이진 탐색
using namespace std;

int N, M;
vector<string> v;
vector<string> ans;
int main(int argc, char** argv){
  std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL); // cin cout 시간 줄이기

  string name;
  
  cin >> N >> M;
  for(int i=0; i<N; i++){
    cin >> name;
    v.push_back(name);
  }

  sort(v.begin(), v.end()); // 첫번째 입력받은 이름 정렬

  for(int i=0; i<M; i++){
    cin >> name;

    if(binary_search(v.begin(), v.end(), name)){
      ans.push_back(name);
    }
  }

  sort(ans.begin(), ans.end()); // 정답 벡터 한번 더 정렬 - 사전순 출력

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

  return 0;
}