[Baekjoon - 1920] 수 찾기

난이도: Silver IV

 

태그

• Binary Search
• Sort

 

풀이

1. 수열 \( A \)가 정렬되어있다면, 원하는 수를 어떻게 빠르게 찾을 수 있을까?

수열 \( A \)가 정렬되어있으니, 이진 탐색을 통해 빠르게 원하는 값의 유무를 판별할 수 있습니다.

 

2. [1]을 사용해서 문제를 풀 수 있을까?

원소 간의 의 순서는 상관이 없으니, \( A \)를 정렬해도 아무런 문제가 없습니다.

그러니, 정렬한 뒤 이진 탐색을 해주면 되겠죠.

 

3. 코드

int arr[100020];
 
void Main(){
    int n; cin >> n; for (int i = 1; i <= n; i++){ cin >> arr[i]; }
    sort(arr+1, arr+n+1);
    int q; cin >> q; while (q--){
        int x; cin >> x;
        int idx = lower_bound(arr+1, arr+n+1, x) - arr;
        cout << (idx <= n && arr[idx] == x) <<endl;
    }
}