[백준] 1920 - 수 찾기 (C++)

문제

1920번: 수 찾기 (acmicpc.net)

1920번: 수 찾기

 

풀이

이분 탐색에 대해 알아볼 수 있는 좋은 문제입니다.

제한 시간이 1초인데, 만약 A 배열과 X를 모두 비교한다면 $O(N^{2})$의 시간 복잡도를 가지게 되므로 시간 초과가 발생합니다.

그러므로 다른 방법을 사용해야 하는데, C++에는 친절하게도 binary_search라는 훌륭한 이분 탐색 함수가 존재합니다.

그저 시작 부분, 끝 부분, 찾을 숫자만을 넣어주면 됩니다.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  int N;
  cin >> N;

  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  sort(A.begin(), A.end());

  int M;
  cin >> M;

  for (int i = 0; i < M; i++) {
    int X;
    cin >> X;

    cout << binary_search(A.begin(), A.end(), X) << "\n";
  }

  return 0;
}