[Silver 4] 1920번 수 찾기

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

1920번: 수 찾기

 

이 문제는 N크기의 배열을 생성하고, 생성한 배열에 N개의 값을 집어 넣는다. 

그후, M개의 수가 N크기의 배열 안에 있는지 확인하는 문제이다.

 

이 문제를 해결하기 위해 map을 사용하였다. map에 N개의 값을 삽입한다. 이때 value는 아무 값이나 사용해도 된다.

즉, key만 사용해서 해결하였다.

 

M개의 입력이 map에 있는지 확인하기 위해 find함수를 사용하였으며

find의 결과가 map의 끝을 가르키지 않는다면 1을 출력하고 끝이라면 0을 출력하였다.

find 함수는 속도가 O(log n)이기 때문에 문제의 제한 시간을 넘지 않을 수 있다.

 

#include<iostream>
#include<map>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin>>N;
    map<int,bool> m;
    for(int i = 0;i<N;i++){
        int input;
        cin>>input;
        m[input] = true;
    }
    int M;
    cin>>M;
    for(int i = 0;i<M;i++){
        int target;
        cin>>target;
        if(m.find(target)!=m.end()){
            cout<<1<<'\n';
        }
        else{
            cout<<0<<'\n';
        }
    }
}