BOJ 1920 - 수 찾기 (C++) + Binary Search

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

최초 풀이: 2023. 12. 15.

재풀이: 2025. 05. 22.

#data_structures #sorting #binary_search #set #hash_set

아이디어

$O(N)$의 시간복잡도를 가진 Linear Search(선형 탐색)를 이용한다면 최악의 경우 $M$ 개의 수에 대해 $A$의 0번째부터 $N-1$ 번 째 원소까지 탐색하게 되므로 $O(NM)$ 의 시간복잡도를 가지게 되어 시간초과가 발생한다.

우리는 단순히 특정 값이 $A$에 포함되었는지의 여부가 궁금하므로 $O(N)$의 시간복잡도를 가진 Binary Search(이진탐색) 을 이용하여 시간복잡도를 개선할 수 있다. Binary Search를 하기 위해서는 먼저 $A$를 정렬해야 하므로 이때 시간복잡도는 $O((N+M)logN)$ 이다.

최초풀이 (Binary Search 직접 구현)

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001];
int N;

int BinarySearch(int x);

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int M, tmp;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }

    sort(arr, arr + N);

    cin >> M;

    for(int i = 0; i < M; i++){
        cin >> tmp;
        if(BinarySearch(tmp) == -1)
         cout << 0 << '\n';
        else
         cout << 1 << '\n';
    }
    return 0;
}

int BinarySearch(int x){
    int low = 0, high = N-1;
    int mid;

    while(low <= high){
        mid = (low + high) / 2;
        if(arr[mid] < x) low = mid + 1;
        else if(arr[mid] > x) high = mid - 1;
        else return mid;
    }
    return -1;
}

재풀이 (내장함수 이용)

/*
auto lower = lower_bound(vec.begin(), vec.end(), key);
-> 벡터에서 최초의 key 이상의 값을 iterator 형태로 저장
auto upper = upper_bound(vec.begin(), vec.end(), key);
-> 벡터에서 최초의 key 초과값을 iterator 형태로 저장장
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

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

    sort(A.begin(), A.end());

    int M;
    cin >> M;

    int num;
    for(int i = 0; i < M; i++){
        cin >> num;
        auto low = lower_bound(A.begin(), A.end(), num);
        if(low - A.begin() == N || *low != num) cout << 0;
        else cout << 1;
        cout << '\n';
    }
    return 0;
}