C++) 백준 10816 숫자 카드 2

입력받은 N개의 수 중에서

또 다른 입력받은 M개의 수가 각각 몇개 존재하는지 찾는 문제이다.

 

입력 개수와 찾는 수 50만 개에 대해 선형탐색을 사용하면 시간초과가 난다.

 

C++에서 Map은 O(log n)의 레드블랙트리로 구현되어있으므로, 이를 이용하면 시간 내로 문제를 해결 할 수 있다.

 

물론 다른 방법, 이분탐색을 사용할 수 있지만 여기선 Map을 이용한 방법을 다루겠다.

 

실제 사용함으로 STL 자료구조에 더 친숙해지기 위함이다.

 

 

map<int,int> 로 key는 각 수(중복X), value값으론 그 개수를 기록한다

 

 

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

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

    int n,input,m;
    map<int,int> map;

    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> input;
        map[input]++;
    }

    cin >> m;

    for(int i = 0; i < m; i++){
        cin >> input;
        cout << map[input] << " ";
    }

    return 0;
}