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

문제링크 : https://www.acmicpc.net/problem/10815

숫자가 매우 크기 때문에 누가 봐도 

브루투 포스로 풀면 안된다는 것을 알 수 있을 것이다.

입력을 받은 배열을 가진채로 입력을 받을때마다

그 값이 미리 받은 배열에 있는지 확인하는 생각을 먼저 할 수 있을 것이다.

그러면 우리가 좋아하는 이분탐색으로 이 문제를 풀 수 있지 않을까 하는 고민을 한다.

이를 위해선 2가지 를 고민해 봐야한다.

① 상근이가 가지고 있는 숫자카드 배열의 Sorting

② Sorting된 배열을 이분탐색으로 검색

1. Sorting

Sorting의 경우 C++ algorithm라이브러리에서 가져다 쓰면 nlogn의 시간 복잡도가 나오니까

우선 별 문제 없이 쓰도록 하자.

2. BinarySearch

BinarySearch의 시간 복잡도 또한 nlogn이므로 큰 문제 없어 보인다.

그렇게 작성한 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
int m;
vector<int> number;
 
bool sort(int num, int first, int last) {
    if (first > last) {
        return false;
    }
 
    int mid = (first + last) / 2;
 
    if (number[mid] == num) {
        return true;
    }
    else if (number[mid] > num) {
        return sort(num, first, mid - 1);
    }
    else {
        return sort(num, mid + 1, last);
    }
 
}
 
int main()
{
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        number.push_back(tmp);
    }
 
    sort(number.begin(), number.end());
 
    scanf("%d", &m);
 
    for (int i = 0; i < m; i++) {
        int tmp;
        scanf("%d", &tmp);
 
        if (sort(tmp, 0, n-1)) {
            cout << "1 ";
        }
        else {
            cout << "0 ";
        }
 
    }
 
}

마지막으로 주의 할 점은

앞서 말했듯이 숫자가 매우 크기 때문에 cin을 쓰게되면 시간 초과가 난다.

(필자는 그것때문에 3번을 틀렸다.)

숫자가 클때는 꼭 scanf를 쓰도록 하자!