백준 10815번: 숫자 카드

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

1. 문제

2. 알고리즘

키워드 - 이분탐색, 구현

초기에 map 에다가 data 를 넣고 find 메소드로 원소가 있는지 확인하는 방법을 사용했으나 시간초과 및 메모리 사용량이 높아서 변경

3. 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <functional>         // greater 사용 위해 필요   #include <string> #include <map> #include <unordered_map> #include <math.h> using namespace std;   // map 사용한 소스  int main() {     ios::sync_with_stdio(false); cin.tie(0);  // scanf 안쓸 경우 쓰세요. Cin 사용시     int n , m;       cin >> n;       unordered_map<int, int> mm;       for(int i =0; i<n; i++) {         int cand; cin>> cand;         mm[cand] = 0;     }          cin >> m;     for(int i =0; i<m; i++) {         int cand; cin >> cand;         if (mm.find(cand) != mm.end()) {             cout << "1" << "\n";         } else {             cout << "0" << "\n";         }     }       return 0; } Colored by Color Scripter

cs

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <math.h>
#include <memory.h>
using namespace std;
 
#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
#define ll long long
 
#define c_reverse(s) reverse(s.begin(), s.end())
#define c_sort(s) sort(s.begin(), s.end())
#define print_vector(v) for(int i=0; i<v.size(); i++) cout << v[i];
 
vector<int> arr;
 
bool bs(int left, int right, int data) {

 
    if (left > right) {
        return false;
    }
 
    int mid = (left + right) / 2;
 
    if (arr[mid] == data) {
        return true;
    }
    else if (arr[mid] < data) {
        // 이자식아 left 를 ++ 가 아니라 mid 의 값에서 올리고 내리고다
        return bs(mid + 1, right, data);
    }
    else {
        // right + 1 하면 oveflow 자나 으아아
        return bs(left, mid - 1, data);
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);  // scanf 안쓸 경우 쓰세요. Cin 사용시
 
    int n, m;    cin >> n;
 
    for (int i = 0; i<n; i++) {
        int data; cin >> data;
        arr.push_back(data);
    }
 
    sort(arr.begin(), arr.end());
 
    cin >> m;
    for (int i = 0; i<m; i++) {
        int data; cin >> data;
 
        if (bs(0, n, data)) {
            cout << "1";// << " ";
        }
        else {
            cout << "0";// << "\n";
        }
        cout << " ";
    }
 
    return 0;
}