BOJ 10815, 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

내 접근

1. 첫 번째로 주어진 카드 숫자에 대해서 두 번째로 주어진 카드 숫자를 찾는거네? Lookup 테이블 형식이 도움이 될 것 같다.
2. 첫 번째로 주어진 카드 숫자가 Key가 되는 Map을 만들고 두 번째 카드 숫자는 Map에 키가 존재하는지 여부를 찾는 식으로 해야 할 것 같다.

구현

#include <iostream>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)

#include <map>

void solve() {
  int n;
  std::cin >> n;

  std::map<int, bool> map;

  int x;
  for (int i = 0; i < n; i++) {
    std::cin >> x;
    map.insert({x, true});
  }

  std::cin >> n;

  for (int i = 0; i < n; i++) {
    std::cin >> x;

    bool exists = map.find(x) != map.end();
    std::cout << exists << " ";
  }
}

int main() {
  IO;
  solve();
  return 0;
}

개선점

Map을 사용했어야 하는가?

• 시간 복잡도 insert: O(log N) find: O(log N)
• N과 M 각각 최대 500,000개의 입력 개수

N log N + M log N
≈ 1,000,000 × log₂(500,000)
≈ 1,000,000 × 19
≈ 19,000,000 트리 연산

• 트리 구조의 캐시 미스와 포인터 추적 비용이 TLE 원인이 될 수 있다.

unordered_set 을 사용하면?

값의 존재 여부만을 찾아야한다면 set을 사용해 볼 수 있겠다.

• 평균 시간 복잡도: O(1)
• 최악: O(N)

정렬 후 이진 탐색은?

중복 없음이 보장 될 경우

• std::vector<int>에 저장하고,

• std::sort로 정렬 후,

• std::binary_search로 탐색

• 시간 복잡도 정렬: O(N log N) 탐색: M log N