10816 - 숫자카드 2

일단 구현해보았다.

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main()
{
    int n, m;
    cin >> n;
    int *arr = new int[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    cin >> m;
    unordered_map<int, int> map;
    unordered_map<int, int> order;
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        map[x] = 0;
        order[i] = x;
    }
    for (int i = 0; i < n; i++)
        map[arr[i]] += 1;
    for (int i = 0; i < m; i++)
        cout << map.at(i) << " ";
}

 

1 ≤ n, m ≤ 500,000인 문제고 map[arr[i]]가 포함된 반복문에서 timeout이 나는 것으로 추정됐다...

 

근데 아니었다.

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

 

이거 넣으니까 됐다.

근데 원래는 메모리 때문에 저렇게 짰던건데

int map[20'000'001]; << 이 정도 쓴다고 메모리 초과가 뜨진 않았다. 놀랍다 백준! 그래서 아래와 같이 완성했다.

 

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

int map[20'000'001];

int main()
{
    map[20'000'001] = {
        0,
    };

    int n, m;
    cin >> n;
    int x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        map[x + 10'000'000]++;
    }
    cin >> m;
    int *result = new int[m];
    for (int i = 0; i < m; i++)
    {
        cin >> x;
        result[i] = map[x + 10'000'000];
    }
    for (int i = 0; i < m; i++)
        cout << result[i] << " ";
}