(매일 BOJ) C++ 2776번 암기왕

이번 문제는 2776번 암기왕이다.

접근법

주어진 수첩 1의 숫자 리스트에 대해 수첩 2의 각 숫자가 존재하는지를 빠르게 판단해야 한다.
단순한 선형 탐색은 시간 초과되므로, 이분 탐색 또는 해시셋을 사용해야 한다.

 

알고리즘 설계

1. 수첩 1의 숫자들을 오름차순 정렬
2. 수첩 2의 각 숫자에 대해 이진 탐색 수행

시간 복잡도

• 정렬: O(N log N)
• M개의 숫자에 대해 각각 O(log N) → 총 O(M log N)

 

작성코드

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    long long T;
    cin >> T;
    for (int i = 0; i < T; i++){
        long long N;
        cin >> N;
        vector<int> v1;

        for (int j = 0; j < N; j++){
            long long num;
            cin >> num;
            v1.push_back(num);
        }
        
        sort(v1.begin(),v1.end());

        long long M;
        cin >> M;
        
        bool b;
        for(int j = 0; j < M; j++){
            long long num;
            cin >> num;
            b = binary_search(v1.begin(),v1.end(),num);
        
            if(b == true) cout << 1 << '\n';
            else cout << 0 << '\n';
        }

        
    }
}