1920 수 찾기

이전에 풀었던 문제이길래 아 머야 또 중복이구만~~ 하고 쉽게 가려다가 풀이도 생각 못했다ㅋㅋㅋㅋ

 

 

일 년 전에 어떻게 풀었냐???

다른사람 코드 슬적 보니깐 va를 이분탐색 하면 된다!

이분탐색은 logN이 걸리니깐 vb에 이분탐색 하니깐 NlogN이 걸린다. 

 

 

 

lower_bound 제대로 이해 못하고 풀었다가 한 번 틀렸다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 1000000

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;


int     main()
{
    int n;
    scanf("%d", &n);
    vector<int> va(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &va[i]);

    int m;
    scanf("%d", &m);
    vector<int> vb(m);
    for (int i = 0; i < m; i++)
        scanf("%d", &vb[i]);

    sort(all(va));

    for (int i = 0; i < m; i++)
    {
        auto res = lower_bound(all(va), vb[i]);
        if (res != va.end())
        {
            if (*res == vb[i])
                printf("1\n");
            else
                printf("0\n");
        }
        else
            printf("0\n");
    }

    return 0;
}

 

처음에 *res == vb[i] 조건 하나만 썼는데 그러면 res가 v.end()라면 문제 된다. (아마 문제가 될것이다 틀렸거든..)

 

그래서 저렇게 if문 두 번 나눠서 썼음