백준, BOJ, 1920번 C++ [CPP]

이 문제 처음에 당연히

for문으로 쉽게 하려다가

입력 숫자보고 바로 접었다.

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

 

 

---

 

#맞은 풀이

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

using namespace std;

int N,M;
//vector<int> vec;

int num[100001];

void binarySearch(int n, int arr[]){
    int low = 0;
    int high = N-1;
    int mid;
    
    while(low <= high){
        mid = (low + high)/2;
        
        if(num[mid] == n){
            cout << '1' << '\n';
            return;
        }else if(num[mid] < n){
            low = mid+1;
        }else if(num[mid]> n){
            high = mid-1;
        }
    }
    cout << '0' << '\n';
    return;
}



int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    for(int i = 0; i<N; i++){
        int a;
        cin >> a;
        num[i] = a;
    }
    
    sort(num, num+N);
    
    cin >> M;
    for(int i = 0; i<M; i++){
        int b;
        cin >> b;
        binarySearch(b, num);
    }

}

 

이 문제는 탐색횟수를, 시간복잡도를 줄여야 했다.

그래서 탐색방법을 생각해봤다.

선형탐색은 시간이 많이 걸리고

어떠한 숫자를 찾는 것은 이진탐색이

O(log N)을 가지므로 엄청 빠르다.

 

BS, BST에서 구현했지만 다시 한 번 복습해야겠다.

 

아 참

근데 이상한 점은

난 처음에 vector로 풀었다.

어차피 연속적 구조고 random access 가 가능하기 때문에 결과가 같을 것이라 생각했는데

vector로는 시간초과가 나고

arr로는 통과가 됐다.