[BaekJoon/백준] 1920번 C++

수 찾기 문제.

 

이중 포문을 돌게 되면 시간복잡도가 O(n^2)이 되어 아마 시간초과가 날 것이다.

 

그렇기 때문에 이진 탐색(바이너리 서치)을 구현했고,

이진 탐색을 사용하기 위해서 전제조건인 오름차순 정렬을 만들어 내기 위해 sort 함수를 사용했다.

+ 이진 탐색 : O(log N)

 

C를 쓰다가 C++로 넘어온 케이스라,

qsort를 쓰려고 했는데 C언어에서의 호환이 안되는지 라이브러리가 먹히지 않는 것 같아서 헤맸는데

C의 qsort보다 C++의 sort가 더 빠르다고 한다.. 그래서 졸지에 더 간단하게 구현할 수 있었다.

+ 퀵정렬 : O(Nlog N)

#include <iostream>
#include <algorithm> // sort 함수 사용 위해

using namespace std;

int ori[100000];
int N;
int key[100000];
int M;

// 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 이진 검색
// 단, 오름차순 정렬이 전제임!!
int bin_search(int a[], int n, int key) {
    
    int pl = 0; // 검색 범위 맨 앞의 인덱스
    int pr = n - 1; // 검색 범위 맨 끝의 인덱스
    int pc; // 검색 범위 한가운데의 인덱스
    
    do {
        pc = (pl + pr) / 2;
        
        if(a[pc] == key)
            return pc;
        else if(a[pc] < key)
            pl = pc + 1;
        else if(a[pc] > key)
            pr = pc - 1;
            
    } while(pl <= pr);
    
    return -1; // 검색 실패
    
}


int main() {
    int i, result;
    
    cin >> N;
    
    for(i = 0; i < N; i++) {
        cin >> ori[i];
    }
    
    
    
    cin >> M;
    
    for(i = 0; i < M; i++) {
        cin >> key[i];
    }
    
    sort(ori, ori + N); // 배열, 배열 + 요소수
    
    for(int i = 0; i < M; i++) {
        
        result = bin_search(ori, N, key[i]);
        
        cout << ((result != -1)?"1\n":"0\n");
    }
    
}

 

배열을 기준으로 sort함수의 오름차순 사용법은

sort(배열이름, 배열이름 + 요소 수) 이다.

 

벡터의 경우에는

sort(v.begin(), v.end())