[백준][10815번][C++] 숫자 카드

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

10815번: 숫자 카드

어느 수들이 주어지고 그 수들이 상근이가 가지고 있는 수 중 존재하는지 알아내는 문제이다.

 

브루트 포스로 모든 수를 비교해보고 푼다면 O(N^2)이므로 TLE가 나는 문제였다.

 

상근이가 가진 수들을 먼저 정렬해주고 이분탐색으로 풀면 되는 문제이다.

 

나는 재귀로 구간을 반반 나눈 다음에  두 구간 중 수가 포함될 가능성이 있는 구간만 재귀로 똑같이 탐색하는 함수를 구현했다.

 

이름은 이분탐색인데 반으로 나눠서 찾는거라 이분탐색으로 이름을 붙이긴 했는데 이분탐색을 많이 구현해보지않아서 이게 이분탐색이 맞는지는 모르겠다.

 

시간복잡도는 기본적으로 정렬을 하므로 O(NlogN)이상이고 재귀 함수의 시간복잡도의 경우에는 N길이의 구간을 반씩 나눠서 무조건 두 구간 중 하나 이하만 탐색하는데 이걸 M번 하므로  O(MlogN)이다.

 

그러므로 N과 M중 더 큰수로 O(NlogN)이거나 O(MlogN)으로 예상된다.

 

N(1 ≤ N ≤ 500,000), M(1 ≤ M ≤ 500,000)이므로 상수 시간복잡도를 가지는 식을 제외하면 최대 대략 9,465,784 번의 연산을 하므로 시간 제한 2초안에는 들어올 것 같다.

 

사실 시간복잡도 계산은 자주해보지를 않아서 틀린점이 있을 수 있을 것 같습니다. 혹시 틀린점이 있다면 댓글로 알려주세요!

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
vector<int> v;

bool binary_search(int lo, int hi, int target) {
    int mid = (lo + hi) / 2;
    
    if(v[lo] == target || v[hi] == target)
        return true;
    if(lo == hi)
        return false;
    
    if(v[lo] <= target  && target <= v[mid])
        return binary_search(lo, mid, target);
    else if(v[mid+1] <= target  && target <= v[hi])
        return binary_search(mid+1, hi, target);
    else
        return false;
}

int main() {
    int N, M, num;
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&num);
        v.push_back(num);
    }
    sort(v.begin(),v.end()); // v 벡터 정렬
    scanf("%d",&M);
    for(int i=0;i<M;i++) {
        scanf("%d",&num);
        if(binary_search(0, N-1, num))
            printf("1 ");
        else
            printf("0 ");
    }
    return 0;
}