수 찾기 1920

문제

접근 방법

정수의 범위가 보통 배열의 범위를 넘어가기에 배열 인덱스를 활용할 순 없다.
N이 10만이기에 배열의 모든 값을 확인하는 N^2 탐색할 수도 없다.
그렇다면 탐색 방법을 바꾸거나 범위를 넘어가도 괜찮은 자료구조를 사용하는 것이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, A;
    cin >> N;
    vector<int> v(N);
    for (int i = 0; i < N; ++i)
        cin >> v[i];
    sort(v.begin(), v.end());
    cin >> N;
    while (N--)
    {
        cin >> A;
        cout << binary_search(v.begin(), v.end(), A) << "\n";
    }
    return 0;
}

풀이

map을 사용하거나 이분 탐색을 활용하면 된다.
이분 탐색을 사용하는 것이 더 빠른 결과를 반환한다.