[백준 1920] 수 찾기

🚀  들어가며...

• 실버 4 문제로 쉬운 문제이다.
• 입력 받은 배열1에 배열2의 요소가 존재하는지 체크하는 문제이다.
• 속도 문제로, 이진 탐색을 사용했다.

 

🔗  문제

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

1920번: 수 찾기

 

📑  내용

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

 

💌 소스코드

#include <iostream>
#include <algorithm>

using namespace std;

void binarySearch(long long key, long long *a, int len){
    int start=0;
    int end=len-1;
    int mid;

    while(end - start >= 0){
        mid = (start + end) / 2;

        if(a[mid] == key){
            cout << "1\n";
            return;
        }
        else if(a[mid] > key){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
    }
    cout << "0\n";
    return;
}

int main(){
    // Don't use the below code with scanf
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int len1, len2;
    cin >> len1;
    long long *a = new long long[len1];
    
    for(int i=0; i<len1; i++)
        cin >> a[i];

    cin >> len2;

    sort(a, a+len1);
    for(int i=0; i<len2; i++){
        long long target;
        cin >> target;
        binarySearch(target, a, len1);
    }

    return 0;
}

 

🙋🏻‍♂️ 후기

사실 알고리즘 문제 풀이를 포스팅할까 말까했다.

약 200개 정도 포스팅을 하지 않았는데, 앞으로 푼 문제는 스스로 정리해야겠다.

(왜냐면.. 풀다 안 풀다 하기도 하거나와, 원리를 까먹을때가 있어서..)