상근이가 가지고 있는 숫자 카드 N개가 있습니다.
이후 M개의 숫자들이 주어지는데, 우리는 이 숫자들이 상근이가 가진 숫자 카드에 포함이 되는지 아닌지를 확인해야 합니다.
문제를 읽고 어떤 알고리즘을 쓸 수 있을지 고민 해봅시다.
우리가 사용할 수 있는 알고리즘은 input의 크기에서 항상 힌트를 얻을 수 있습니다.
이 문제에서 숫자 M개에 대해 상근이가 가진 카드에 포함되는 숫자인지 아닌지를 확인해야 하기 때문에
숫자 카드에 포함되는지 판단하는 시간복잡도 곱하기 O(M) 로 시간 복잡도가 계산됩니다.
여기서 M은 최대 500,000개 / 상근이가 가진 숫자 카드의 개수 N은 최대 500,000개입니다.
자 그러면 이제 숫자 카드에 포함되는지 판단하는 시간복잡도에 어떤 값이 올 수 있을지 찾아보겠습니다.
이 경우 총 시간복잡도는 O(M) * O(N)이되고, 약 250,000,000,000번의 연산이 필요합니다.
시간제한 2초에 턱없이 부족한 연산 개수이죠.
(🍯 TIP ! 코딩테스트 문제를 풀 때 연산 1억개가 약 시간 1초 정도로 계산하면 OK!)
이 문제에서는 O(N)의 시간복잡도로 탐색이 불가능함을 알게 되었지만,만약 O(N)으로 탐색을 한다면?
→ 상근이가 가진 모든 숫자 카드를 한개씩 비교하며 탐색하는 방법이 대표적인 O(N)의 시간복잡도를 가집니다.