백준 실버4 1920 수 찾기

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

 

 

이 문제는 다음과 같이 풀 수 있다.

1. 배열의 길이를 입력 받는다.

2. 해당 배열에 들어갈 원소들을 순차적으로 입력 받는다

3. 비교할 배열의 길이를 입력 받는다
   (굳이 배열에 담지 아니해도 된다, 설명 편의상 배열이라고 가정하였다.)

4. 먼저 생성된 배열과 비교할 배열의 원소와 일치한다면 1을, 아니라면 0을 출력한다.

 

해당은 문제는 탐색을 통해 풀 수 있다.

필자는 이진 탐색으로 풀었다.

using namespace std;


int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);

    int n;

    cin >> n;
    vector<int> inputArr(n);

    for (int i = 0; i < n; i++) {
        cin >> inputArr[i];
    }

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        int start = 0, end = inputArr.size() - 1, target = 0;
        bool find = false;

        cin >> target;

        while (start <= end)
        {
            int midIdx = (start + end) / 2;
            int midVal = inputArr[midIdx];

            if (midVal > target) {
                end = midIdx - 1;
            }
            else if (midVal < target) {
                start = midIdx + 1;
            }
            else {
                find = true;
                break;
            }
        }
        if (find) {
            cout << 1 << "\n";
        }
        else {
            cout << 0 << "\n";
        }
    }
    
    return 0;
}