[백준] 10815 숫자 카드 ( C++)

 

 

 

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

10815번: 숫자 카드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector <int> input;
vector <int> right;
int main(void) {
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        int q;
        cin >> q;
        input.push_back(q);
    }
    input.push_back(999999999);
    cin >> m;
    for (int i = 0; i < m; i++) {
        int q;
        cin >> q;
        auto it = find(input.begin(), input.end(), q);
        if (it == input.end()) {
            cout << "0 ";
        }
        else {
            cout << "1 ";
        }
    }
    return 0;
}

맨 처음에는 이분탐색을 사용하지 않고 위의 방법처럼 find를 이용한 문제를 풀어봤는데

시간초과가 떠서 이분탐색으로 다시 풀어봤다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector <int> input; // n의 갯수만큼 입력받을 곳
vector <int> ri; // m의 갯수만큼 입력받을 곳
vector <int> ox; // 1 0 저장공간
int main(void) {    
    cin >> n;
    for (int i = 0; i < n; i++) {
        int q;
        cin >> q;
        input.push_back(q);
    }    
    

    sort(input.begin(), input.end());
    //정렬해줌 -> 이분탐색을 위해
    

    cin >> m;
    for (int i = 0; i < m; i++) {
        int q;
        cin >> q;
        ri.push_back(q);
    }


    for (int i = 0; i < m; i++) {
        int start = 0;
        int end = input.size();
        int mid = 0;
        //이분탐색 부분
        while (1) {
            if (start >= end) {
                ox.push_back(0);
                break;
            }
            mid = (start + end) / 2;
            if (input[mid] == ri[i]) {
                ox.push_back(1);
                break;
            }

            if (input[mid] > ri[i]) {
                end = mid;
            }
            if (input[mid] < ri[i]) {
                start = mid + 1;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        cout << ox[i] << " ";
    }    

    return 0;
}