Beakjoon 10815 숫자 카드

10 Feb 2021 in Algorithm

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

나의 풀이

이 문제는 가장 기본적인 이진 탐색문제로 N개의 숫자 카드를 오름차순으로 정렬한 뒤 이분 탐색을 수행하여 M개의 각각의 정수와 일치한지 확인할 수 있습니다.

풀이 코드 : 10815 숫자 카드

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

using namespace std;

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

    int N,M,num;
    vector<int> arr;
    vector<int> q;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>num;
        arr.push_back(num);
    }

    cin>>M;
    for(int i=0;i<M;i++){
        cin>>num;
        q.push_back(num);
    }
    
    sort(arr.begin(), arr.end());

    vector<int> answer;

    for(int i=0;i<M;i++){
        int start = 0;
        int end = N-1;
        int mid;
        bool exist = false;
        while(start <= end){
            mid = (start+end)/2;

            if(arr[mid] == q[i]){
                exist = true;
                break;
            }

            if(arr[mid] < q[i]){
                start = mid + 1;
            }
            else{
                end = mid - 1;
            }
        }
        if(exist){
            answer.push_back(1);
        }
        else{
            answer.push_back(0);
        }
        cout<<answer.back()<<" ";
    }

    

}

채점결과