1920번-수 찾기

문제

---

주어진 정수들 안에 특정 정수들이 있는지 1 또는 0으로 확인하면 된다

쉬울 것 같지만, 정수들이 엄청 많은게 문제

문제 해결을 위한 준비물

---

sort - 2진 탐색을 하기 위해 순차열 만들기 위함

scanf / printf - 입력을 빠른 속도로 받기 위함 (cin / cout는 느려서 시간초과)

코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int binarySearch(int numbers[], int end, int key){
    int left = 0, right = end;
    int mid;

    while(left <= right){
        mid = (left + right) / 2;

        if(key == numbers[mid]) return 1;
        else if(key < numbers[mid]) right = mid -1;
        else if(key > numbers[mid]) left = mid +1;
    }

    return 0;
}

int main()
{
    int n, m, temp;

    cin >> n;
    int numbers[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &numbers[i]);
    }
    sort(numbers, numbers + n);

    cin >> m;
    for(int i = 0; i < m; i++){
        scanf("%d", &temp);
        printf("%d\n", binarySearch( numbers, n - 1, temp));
    }

    return 0;
}

풀이

---

탐색과 속도, 두 개의 문제를 해결하면 된다

탐색은 2진 탐색 알고리즘 활용.

왜 2진 탐색을? => 어떤 요소가 어떤 데이터를 갖고 있는지 모를 때, 가장 이상적인 탐색 알고리즘이기 때문이다

 

속도은 vector -> array , cin / cout -> scanf / printf

위 두개는 속도는 느리지만 여러 편의성을 제공해준다.