[BOJ_C++] 2776번 : 암기왕

# 문제

 

# 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

int search(int* list, int key, int size) {
    int low = 0, high = size - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (list[mid] == key)
            return 1;
        if (list[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return 0;
}

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

    int t, n, m, key; cin >> t;
    for (int tc = 0; tc < t; tc++) {
        cin >> n;
        int* list1 = new int[n];
        for (int i = 0; i < n; i++) cin >> list1[i]; sort(list1, list1 + n);
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> key;
            if (search(list1, key, n)) cout << "1\n";
            else cout << "0\n";
        }
    }

    return 0;
}

• 테스트케이스를 입력받고 테스트케이스만큼 for문을 돌며 수첩1에 있는 숫자가 수첩2에 적혀있는 숫자가 있는지 확인할 것이다.
• 수첩1에 적을 숫자를 입력받은 후 정렬한다.
• 수첩2에 적을 숫자를 입력받고 그 값을 key로 넘겨줘 수첩1에서 이분탐색을 통해 수첩1에 존재하는지 찾을 것이다.
• 만약 이분탐색을 통해 key를 찾는다면 1을 반환하고, 아니라면 0을 반환하고 값에따라 바로 출력한다.

 

# 결과