백준_1764_듣보잡

 

 

문자열을 n번 ,m번 입력받아서 겹치는 문자열과 그 개수를 출력하는 문제입니다.

 

단순하게 문자열을 입력받아서 하나하나씩 비교하게 되면 시간이 너무 오래걸려 시간 초과가 날 것입니다.

 

그렇다면 어떻게 해야할까요??

 

해시를 기반으로 하는 탐색을 이용하면 됩니다.

 

해시는 고유값을 가지기에  데이터의 삽입, 삭제, 탐색 모두 평균적으로 O(1) 입니다.

 

이번에는 unordered_set 을 이용해보겠습니다.

 

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  int n = 0, m = 0;
  cin >> n >> m;
  unordered_set<string> s;
  string str;
  for (int i = 0; i < n; i++) {
    cin >> str;
    s.insert(str);
  }

  int count = 0;
  vector<string> result;
  for (int i = 0; i < m; i++) {
    cin >> str;
    if (s.find(str) != s.end()) {
      result.push_back(str);
      count++;
    }
  }
  std::sort(result.begin(), result.end());

  cout << count << '\n';
  for (int i = 0; i < result.size(); i++) {
    cout << result[i] << '\n';
  }
  return 0;
}

사용법은 간단합니다.

unordered_set 헤더를 추가해주고 

벡터를 사용하는 방식과 비슷하게 사용해주면 됩니다.

 

이렇게 되면 탐색이 매우 빨라 시간이 초과가 안나는 모습을 볼 수 있습니다.