[백준] 1920번 - 수 찾기 (실버 4)

문제

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

1920번: 수 찾기

 

---

 

접근 방식

• 정렬 후 이진탐색 구현 매개변수로 정렬된 벡터 전달 -> 10% 시간 초과
• 입출력 속도 개선 -> 10% 시간 초과
• 정렬된 벡터를 전역 변수로 접근(매개변수로 전달하는 과정에서 시간이 많이 걸릴 수 있다고 함) -> 통과

---

 

코드

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

using namespace std;

vector<int> func_1920_An;

int func_1920_isExist(int find_value) {
    int res = 0;
    int start_index = 0, end_index = func_1920_An.size();
    int index = (int)floor((start_index + end_index) / 2);

    while(start_index < end_index) {
        if (find_value == func_1920_An.at(index)) {
            res = 1;
            break;
        }

        if (start_index == index){
            break;
        }

        if (find_value > func_1920_An.at(index)) {
            start_index = index;
        }

        if (find_value < func_1920_An.at(index)) {
            end_index = index;
        }

        index = (int)floor((start_index + end_index) / 2);
    }

    return res;
}


int main() {
    int n, m, tmp;
    vector<int> Am;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        func_1920_An.push_back(tmp);
    }

    sort(func_1920_An.begin(), func_1920_An.end());

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

    for (auto m_tmp : Am) {
        cout << func_1920_isExist(m_tmp) << "\n";
    }
    
    return 0;
}

---

 

결과