[백준 / C++] 1920번 수 찾기

문제 재정의 및 추상화

결론: 입력되는 수가 어떤 수열에 포함되는지 알아내라.

문제 접근 방식

입력 수가 크지만 시간 제한은 1초이므로 선형 탐색은 시간 초과가 날 수 있다.

-> 이진 탐색을 써보자!

해법을 찾는데 결정적이었던 깨달음

📌 배열을 꼭 두 개 쓸 필요는 없다!

문제 풀이 로직

1. 비교용 수열을 입력받는다.
2. 이진 탐색을 위해 해당 수열을 정렬한다.
3. 확인할 숫자들을 입력받으며 아래의 이진 탐색을 진행한다.
   3-1. 시작 인덱스와 끝 인덱스를 초기화한다.
   3-2. 끝 인덱스가 시작 인덱스보다 크거나 같을 때까지 중간 인덱스의 값이 확인할 숫자와 같으면 1을 출력하고 반복문을 나온다.
   3-3 끝 인덱스가 시작 인덱스보다 작으면 시작 인덱스를 늘리고, 크면 끝 인덱스를 줄이며 반복문을 계속 돈다.
4. 위 반복문을 모두 통과하면 0을 출력한다.

문제 풀이

#include <bits/stdc++.h>
using namespace std;

int arrN[100001];

void binarySearch(int n, int m){
    int start = 0;
    int end = n - 1;

    while(end >= start){
        int mid = (start + end) / 2;

        if(arrN[mid] == m){
            cout << "1" << "\n";
            return;
        }
        else if(arrN[mid] < m) start = mid + 1;
        else if(arrN[mid] > m) end = mid - 1;
    }

    cout << "0" << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, tmp;

    cin >> n;
    for(int i = 0; i < n; i++) cin >> arrN[i];

    sort(arrN, arrN + n);

    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> tmp;
        binarySearch(n, tmp);
    }

    return 0;
}