1920번

1920번 - 수 찾기

만약 이중포문으로 돌 경우에는 시간초과가 발생하기 때문에 이분탐색을 이용해서 문제를 풀었다.

그러면 포문에서 M번 돌고, 소트된 배열을 이진 탐색하는데 logN 이기 때문에 시간안에 돌 수 있을거라고 생각했다.

O(MlogN) 이 되므로 시간에 통과할 수 있게 된다.

lower_bound 와 upper_bound 를 이용해서 해당하는 값을 찾고, l 과 r 이 같을 경우는 존재하지 않으므로 0을 출력하고

나머지 경우에는 존재하므로 1을 출력한다.

<정답 코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n;
    vector<int> have(n);
    for (int i = 0; i < n; i++)
    {
        cin >> have[i];
    }
    sort(have.begin(), have.end());
    cin >> m;
    vector<int> look(m);
    for (int i = 0; i < m; i++)
    {
        cin >> look[i];
    }
 
    for (int i = 0; i < m; i++)
    {
        auto l = lower_bound(have.begin(), have.end(), look[i]);
        auto r = upper_bound(have.begin(), have.end(), look[i]);
 
        if (r - l == 0)
        {
            cout << "0\n";
        }
        else
        {
            cout << "1\n";
        }
    }
 
 
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}