BOJ 1920 수 찾기 / C++, 시간 초과 방지 팁

문제 링크 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

문제 풀이

첫 번째 배열에 두 번째 배열 값들이 존재하는지 찾는 문제이다.

이진 탐색을 사용하기 위해 첫 번째 배열들은 정렬을 해준다.

두 번째 배열들은 입력받자마자 이진 탐색을 통해 해당 값들이 첫 번째 배열에 있는지 확인한다.

 

C++에서 시간 초과를 방지하려면

(1) 

ios_base::sync_with_stdio(false);

cin.tie(nullptr); cout.tie(nullptr); 을 main 문에 넣어줘서 입출력 속도를 빠르게 해주는 방법과

(2)

endl 대신 '\n'을 쓰는 방법이 존재한다.

 

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;

int BinarySearch(int arr[], int low, int high, int target){
    while(low <= high){
        int mid = (low + high) / 2;
        if(arr[mid] == target) return 1;

        if(arr[mid] > target) high = mid - 1;
        else low = mid + 1;
    }

    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int n;
    int arr[100001];
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    sort(arr + 0, arr + n);

    int t;
    cin >> t;
    int testArr[100001];
    for(int i=0;i<t;i++){
        cin >> testArr[i];
        cout << BinarySearch(arr, 0, n - 1, testArr[i]) << '\n';
    }
}