(C++) - 백준(BOJ) 1920번 : 수 찾기 답

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

이분탐색을 구현해보는 문제였습니다.

 

풀이방법

 1. STL binary_search함수를 사용해 key값을 찾았다면 1을 아니라면 0을 출력하도록 합니다.

 2. 직접 이분탐색을 구현하는 방법도 있습니다.

 

* 입출력이 많으므로 c와 동기화를 풀어줘야 시간초과가 나지 않습니다. 

 

Code

1. STL 사용

#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
int n,m;
vector <int> a;

int main(){
    fastio;
    cin >> n;
    for(int i = 0,x; i < n; i++) { cin >> x, a.push_back(x); }
    sort(a.begin(), a.end());
    cin >> m;
    for(int i = 0; i < m; i++){
        int x;
        cin >> x;
        cout << binary_search(a.begin(),a.end(),x) << '\n';
    }
}

 

2. 직접구현

#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n,m,x;
int a[100001];

int binarySearch(int x){
    int left = 0;
    int right = n - 1;
    while(left <= right){
        int mid = (left + right) / 2;
        if(a[mid] < x) left = mid + 1;
        else if(a[mid] > x) right = mid - 1;
        else return 1;
    }
    return 0;
}
int main(){
    fastio;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    cin >> m;
    for(int i = 0; i < m; i++){
        cin >> x;
        cout << binarySearch(x) << '\n';
    }
}