백준 1920 - 수 찾기

문제 풀이

범위 1~10만개의 숫자들 중에서 M개의 주어진 값이 존재하는지 확인하는 문제이다. 일반적인 탐색을 진행할 경우 O(N*N)의 시간복잡도를 갖게 되므로 O(logN)의 시간복잡도를 갖는 이분 탐색을 이용해 문제를 해결하도록 한다.

전체 소스

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

int binarySearch(vector<int>& arr, int value) {
    int begin = 0;
    int end = arr.size() - 1;

    while (begin <= end) {
        int mid = (begin + end) / 2;
        int midValue = arr[mid];

        if (value == midValue) {
            return 1;
        } else if (value > midValue) {
            begin = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return 0;
}

vector<int> solution(vector<int> arr, vector<int> values) {
    vector<int> results;

    for (int valuesIndex = 0; valuesIndex < values.size(); valuesIndex++) {
        int result = binarySearch(arr, values[valuesIndex]);
        results.push_back(result);
    }

    return results;
}

int main(void) {
    int n, m;
    vector<int> arr;
    vector<int> values;
    cin >> n;

    arr = vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    cin >> m;
    values = vector<int>(m);
    for (int i = 0; i < m; i++) {
        cin >> values[i];
    }

    vector<int> results = solution(arr, values);

    for (int value : results) {
        cout << value << '\n';
    }

    return 0;
}