[백준 10816] 숫자 카드 2

문제

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

10816번: 숫자 카드 2

풀이

map을 이용해서 풀었다.

개수가 50만개라서 시간초과를 걱정하고 풀었는데, 아슬아슬했던 것 같다.

이분 탐색을 쓰면 더 효율적으로 풀 수 있는듯? map 자체도 이분 탐색이긴 하다만

upper_bound와 lower_bound를 쓰면 더 빠르게 풀 수 있다고 함.

소스 코드

map으로 해결

#include<iostream>
#include<map>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    map<int, int> myMap;
    int n, m;
 
    cin >> n;
    int num;
    for (int i = 0; i < n; i++)
    {
        cin >> num;
        myMap[num]++;
    }
 
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> num;
        cout << myMap[num] << ' ';
    }
 
    return 0;
}

bound로 해결

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    vector<int> v;
    int n, m;
 
    cin >> n;
    int num;
    for (int i = 0; i < n; i++)
    {
        cin >> num;
        v.push_back(num);
    }
 
    sort(v.begin(), v.end());
 
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> num;
        cout << upper_bound(v.begin(), v.end(), num) - lower_bound(v.begin(), v.end(), num) << ' ';
    }
 
    return 0;
}