백준 1920번, 수 찾기

백준 1920번 c++ 문제풀이

문제: N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력: 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

풀이:

1. sort와 이분 탐색을 이용한다.
2. 먼저 A[1] ~ A[n]을 오름차순으로 정렬 한다.
3. M개 입력 받은 수가 A배열에 있는지 이분 탐색을 이용해 확인한다.

코드:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

int n, input,m;
cin >> n;
vector<int> v;
vector<int> v1;

for(int i=0;i<n;i++){
    cin >> input;
    v.push_back(input);
}
sort(v.begin(), v.end());  //오르차순 정렬

cin >> m;

for(int i=0;i<m;i++){
    cin >> input;
    v1.push_back(input);
}



for(int i=0;i<m;i++){
    int high = v.size()-1,low = 0;
    int mid;
    while(low<=high){
        mid = (high + low)/2;
        if(v[mid] == v1[i]){    
            cout << 1 << "\n";
            break;
        }else if(v[mid] < v1[i]){
            low = mid+1;
        }else if(v[mid] > v1[i]){
            high = mid-1;
        }

        if(high < low){
            cout << 0 << "\n";
        }
    }
}

return 0;
}

이분 탐색을 잘 구현 한다면 쉽게 풀수 있는 문제였다. 정렬은 stl sort를 사용했다.