[백준 2776번] 암기왕 (C++)

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

2776번: 암기왕

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, N, M;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T >> N;
    while(T--)
    {
        cin >> N;
        map<int, int>m;
        while(N--)
        {
            int n;
            cin >> n;
            m[n]++; //수첩 1 표시
        }
        cin >> M;
        while(M--)
        {
            int n;
            cin >> n;
            cout << ((m[n]) ? 1 : 0) << "\n"; //있었다면 1, 없었다면 0
        }
    }

    return 0;
}

 

map을 사용해도되고, 이분탐색을 사용해도 되는 문제이다.

map을 사용하는 경우에는 수첩 1에 대해 입력받은 수를 Key로하여 Value 값을 표시해준다.

이후 수첩 2에 대해 입력받은 수를 Key로 넣었을 때 Value가 존재하면 있다는 뜻이므로 1을, 아니라면 0을 출력해준다.

 

이분탐색을 사용한 경우에는 수첩 1에 대해 배열로 입력받고 정렬해준 뒤, 이후 입력받은 수첩 2에 대해 입력받을 때마다 이분탐색을 돌려 수첩 1에 대한 값이 있는지 체크해주면 된다.