백준 10815 - 숫자카드 - 이분 탐색

문제

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

풀이전략

1. 카드의 개수가 매우 크므로 또한 카드에 적혀있는 숫자도 매우 크므로 반드시 long long 을 써줘야한다? 아니다 이거는 더하거나 빼주는게 아니기때문에 int로 충분하다. 이를 항상 생각하고 문제를 풀어야한다.
2. 카드의 개수가 커서 이분 탐색으로 문제를 해결해야 시간초과에 걸리지 않는다.
3. input들을 먼저 정렬해주고 그에따라 이분탐색을 진행한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, M;
vector<int> card;

int BinarySearch(int lt, int rt, int num){
    if(lt > rt) return 0;
    else{
        int mid = (lt+rt) / 2;
        if(card[mid] == num){
            return 1;
        }
        else if(card[mid] > num){
            return BinarySearch(lt, mid-1, num);
        }
        else{
            return BinarySearch(mid+1, rt, num);
        }
    }
}

int main(){
    /// cin.tie(0)을 안썻다고.... 시간초과가 떳다....
    /// 앞으로 그냥 scanf를 써야하는것인가..?
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    int tmp;
    for(int i=0; i<N; i++){
        cin >> tmp;
        card.push_back(tmp);
    }
    sort(card.begin(), card.end());
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> tmp;
        
        cout << BinarySearch(0, card.size()-1, tmp) << '\n';
    }
    
    return 0;
}

소감

cin.tie(0)때문에... 시간초과에 걸렸는데... 이를 디버깅하느라 너무 오래걸렸다 저번에 endl때문에 당했는데 또 이렇게 당하네 ㅋㅋㅋㅋㅋ. 그냥 앞으로는 scanf와 printf를 사용할것이다.