백준-1920 수 찾기 해답 및 풀이

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

핵심 아이디어

1. 이진 탐색으로 검색하면 검색 시간을 줄일 수 있다. (이진 탐색을 위해 정렬은 필수)

2. 정렬은 algorithm 라이브러리의 sort 함수를 사용. (충분히 빠르다. n log n)

3. 빠른 출력을 위해 표준 출력 설정값을 바꾼다. 링크: https://www.acmicpc.net/problem/15552 

내가 실수했던 것

1. vector의 size()의 리턴 타입이 unsigned long이여서 계산을 unsigned long으로 하였더니 계산 오류가 발생했다.

2. 이진 탐색의 범위를 이상하게 설정하였다. ( ex. end_idx = cur_idx - 1;을 end_idx = cur_idx로 또 계산하게 되었다.)

c++ 코드

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

using namespace std;

bool binarySearch(vector<int>& v, int x) {     //이진 탐색
    int cur_idx = 0;
    int begin_idx = 0;
    int end_idx = v.size() - 1;

    while(begin_idx <= end_idx) {
        cur_idx = ( begin_idx + end_idx ) / 2;

        if(v[cur_idx] == x) {
            return true;
        } else {
            if(v[cur_idx] > x)
                end_idx = cur_idx - 1;
            else
                begin_idx = cur_idx + 1;
        }
    }

    return false;
}

void inputVector(vector<int>& v, int size) {
    int dump;

    for(int i = 0; i < size; i++) {
        cin >> dump;
        v.push_back(dump);
    }
}

int main() {
    cin.tie(NULL);                    // 표준 입출력 설정
    ios::sync_with_stdio(false);


    int N, M;

    cin >> N;
    vector<int> A;
    inputVector(A,N);

    cin >> M;
    vector<int> m;
    inputVector(m,M);

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

    for(int i = 0; i < m.size(); i++) {
        cout << binarySearch(A, m[i]) << "\n";
    }

    return 0;
}