boj1764-풀이

boj.kr/1764 듣보잡 (문제)

풀이

---

해시 테이블과, 이분탐색

듣도/보도 명단은 각각 최대 50만개, 최대 길이 20의 중복없는 문자열이 주어집니다.
문자열의 최대 길이가 작은 값인 20으로 정해져 있어 해싱을 할 때 사용하기로 결정했습니다.
그렇게 길이와 시작 문자를 통해서 해싱을 하고, 저장을 한 후, 정렬했을 때의 위치를 이분탐색으로 찾아 삽입하도록 했습니다.
str_hash_table클래스의 insert 메소드는 내부의 table에서 적절한 위치를 찾아 문자열을 삽입하는 기능을 합니다.

str_hash_table클래스의 find 메소드는 내부의 table에 해당 문자열이 존재하는지 여부를 파악해서 반환하는 역할을 합니다.

1. 듣도 명단을 입력받아 해시테이블_듣도에 삽입하고,
2. 보도 명단을 입력받아 다른 해시테이블_보도에 삽입합니다.
3. 듣도의 명단을 하나하나 순회하면서, 이분탐색을 통해 보도 명단에 있는지 확인합니다. (이때, 듣도의 명단이 보도의 명단보다 많다면 반대로 진행하면 시간복잡도를 줄일 수 있습니다.)
   $O(n)O(logm)$에서 $O(m)O(logn)$

조금 아쉬운 점 : find와 insert에서 이분탐색을 하면서 중복되는 코드가 존재하는데, 이 부분을 합쳤더라면 깔끔했을 듯

구현

---

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

class str_hash_table
{
public:
  // table
  vector<string> table[20][26];
  void insert(string str)
  {
    int len = str.length() - 1;
    int index = str[0] - 'a';
    int start = 0, end = table[len][index].size();
    // binary search
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (table[len][index][mid] == str)
      {
        table[len][index].insert(table[len][index].begin() + mid, str);
        return;
      }
      else if (table[len][index][mid] < str)
        start = mid + 1;
      else
        end = mid;
    }
    table[len][index].insert(table[len][index].begin() + start, str);
  }
  bool find(string str)
  {
    int len = str.length() - 1;
    int index = str[0] - 'a';
    int start = 0, end = table[len][index].size();
    // binary search
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (table[len][index][mid] == str)
        return true;
      else if (table[len][index][mid] < str)
        start = mid + 1;
      else
        end = mid;
    }
    return false;
  }
};

int main()
{
  int n, m;
  cin >> n >> m;
  str_hash_table t1, t2;
  vector<string> result;
  for (int i = 0; i < n; i++)
  {
    string str;
    cin >> str;
    t1.insert(str);
  }
  for (int i = 0; i < m; i++)
  {
    string str;
    cin >> str;
    t2.insert(str);
  }
  for (int i = 0; i < 20; ++i) {
    for (int j = 0; j < 26; ++j) {
      for (const string &s : t1.table[i][j]) {
        if (t2.find(s)) {
          result.push_back(s);
        }
      }
    }
  }
  sort(result.begin(), result.end());
  cout << result.size() << '\n';
  for (const string &s : result)
    cout << s << '\n';
  return 0;
}