baekjoon - (수 찾기)

문제 번호 : 1920번

난이도 : Silver 4

시간 제한메모리

1 초

128 MB

 

문제

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보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

 

 

풀이) 이 문제 같은 경우

주어진 M개의 수 안에 값이 N개 안에 있는지를 판별하는 문제이다.

 이 문제 같은 경우 풀이는 어렵지 않다. 하지만!! 시간 제한이 1초인 상태에서 그대로 순회하면서 탐색할 경우 최악의 경우 100,000번 * 100,000번 이라서 10^10이 나오게 된다. 하지만 1초는 10^8 이기 때문에 전체 탐색은 타임오버에 걸리게 된다. 이럴 경우 이진 탐색으로 풀면 10(N) * (10logn)으로 풀수 있다.

 

이진 탐색 알고리즘을 사용할 때 주의사항이 있다. 먼저 이진 탐색을 사용할 경우 정렬이 되어 있는 상태에서만 가능하다.

그렇다면 입력을 받고 탐색을 할 배열에 대해서 정렬을 해놔야 한다는 것이다.

 

필자는 M의 i 번째를 타겟으로 잡고, N의 수를 정렬하여 N을 탐색할 것이다.

 

코드)

using namespace std;
vector<int> arr1;
vector<int> arr2;

//이진탐색
int Bsearch(int target){
    int low = 0;
    int high = arr1.size()-1;
    int mid;
    int ret = 0;
    while(low <= high){
        mid = (low + high) / 2;
        
        if(target == arr1[mid]){
            ret = 1;
            break;
        }else if(target < arr1[mid]){
            high = mid - 1;
        }else if(target > arr1[mid]){
            low = mid + 1;
        }
    }
    return ret;
}
int main() {
    int N;
    cin >> N;
  
    for(int i=0; i<N; i++){
        int n;
        cin >> n;
        arr1.push_back(n);
    }
    int M;
    cin >> M;
    
    for(int i=0; i<M; i++){
        int m;
        cin >> m;
        arr2.push_back(m);;
    }
    
    sort(arr1.begin(), arr1.end());
    
    
    for(int i=0; i<M; i++){
        cout << Bsearch(arr2[i]) << "\n";
    }
    return 0;
}

 

 

*이진 탐색은 정렬된 수에서 반씩 제거하여 탐색을 하기 때문에 정렬되어 있는 수의 탐색에서는 정말 효율적이다.