인프런 커뮤니티 질문&답변

std::set은 레드블렉 트리로 구현하여 삽입, 삭제, 검색 모두 O(logN)인걸로 알고있습니다. 이분 탐색도 시간 복잡도가 O(logN)인데 왜 std::set을 사용하면 더 느린지 궁금합니다.

아래는 풀이 소스코드입니다.

#include <bits/stdc++.h>

using namespace std;

int32_t t, n, m, tmp;
set<int32_t> s;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin >> t;

  while (t--) {
    cin >> n;
    s.clear();

    for (int32_t i = 0; i < n; ++i) {
      cin >> tmp;
      s.emplace(tmp);
    }

    cin >> m;

    for (int32_t i = 0; i < m; ++i) {
      cin >> tmp;

      if (s.contains(tmp)) {
        cout << "1\n";
      } else {
        cout << "0\n";
      }
    }
  }

  return 0;
}