[1920] 수 찾기 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N; cin >> N;

    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    int M; cin >> M;

    for (int i = 0; i < M; i++) {
        bool find = false;
        int tmp;
        cin >> tmp;

        int s = 0;
        int e = A.size() - 1;

        while (s <= e) {
            int mid = (s + e) / 2;

            if (A[mid] > tmp) e = mid - 1;
            else if (A[mid] < tmp) s = mid + 1;
            else {
                find = true;
                break;
            }
        }
        if (find) cout << 1 << "\n";
        else cout << 0 << "\n";
    }

    return 0;
}

 

1. 시간 제한이 1초, 자연수 N이 100,000개, 찾아야 하는 수가 100,000개 이므로 이중 for문을 사용하면 시간 초과

=> 이진 탐색을 사용한 O(NlogN)의 시간 복잡도로 문제를 풀어야 함

2. vector를 생성하여 M을 저장하는 방법이 아닌 정수형 tmp를 생성해 수를 임시로 저장하는 방식을 사용

 

 

endl을 사용하여 시간초과가 났던 문제