숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1

3 0 0 1 2 0 0 2

 

이 문제도 map으로 풀어야겠다는 생각을 했다. 

#include <iostream>
#include <map>
 
using namespace std;
 
int main() {
   map<int, int>m;
    int N, M, card;
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin  >> card;
        m[card]++;
    }
    cin >> M;
    for(int i = 0; i < M; i++) {
        cin >> card;
        cout << m[card] << " ";
    }
}

항상 구현하던 방식으로 풀었는데 시간 초과가 나버렸다. 그래서 알아보다가 unordered_map를 사용하면 시간 초과를 막을 수 있다는 것을 보고 사용해봤다. 또 시간 초과되었다.

입출력 양이 많아지면 소모시간이 많아져서 시간 초과가 발생할 수 이도 있다고 하여

ios::sync_with_stdio(false);

를 사용해 stream 동기화를 비활성화 한다. 입출력 시간을 절약할 수 있다.

cin.tie(NULL); 

를 통해서는 입출력 연결을 끊어주어 시간이 단축된다.

#include <iostream>
#include <unordered_map>
#include <cstdio>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
 
    unordered_map<int, int> m;
    int N, M, card;
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> card;
        m[card]++;
    }
 
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> card;
        cout << m[card] << " "; 
    }
 
    return 0;
}
 

그래서 최종본은 이렇게 된다.