[BOJ] #10816 숫자카드2

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

10816번: 숫자 카드 2

---

10815번 문제와 비슷한 듯 다른 문제다. 다른 점이라 하면, 시간제한이 1초라는 점인데, 처음에 10815번 문제와 같이 set 컨테이너를 이용하여 풀었더니 시간초과가 나왔다. set에서 find나 count를 쓴다 해도 O(logN)의 시간복잡도를 가지는데, 이것이 반복문 안에서 움직이다 보니 시간초과가 뜨는 듯했다. 따라서 map을 사용하여 find나 count 없이 최대한 cost가 낮은 방향으로 풀었다. 딱 보기에 10815번과 같다고 그냥 set을 이용하여 풀고 헤매느라 시간이 많이 걸린 문제였다.

#include <iostream>
#include <map>

using namespace std;

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

    int N;
    cin >> N;

    map<int, int> m;
    for (int i=0; i<N; i++) {
        int a;
        cin >> a;
        m[a]++;
    }

    int M;
    cin >> M;

    for (int i=0; i<M; i++) {
        int a;
        cin >> a;

        cout << m[a] << ' ';
    }

    return 0;
}

---

m[a]++;​

map을 이용하여 m[a]++; 같은 수식으로 특정 key값이 그 집합에서 포함된 횟수를 쉽게 나타낼 수 있다. map에서 key값이 value번 나왔다는 의미. set container의 count를 써도 되긴 하지만, 이쪽이 cost가 적게 걸린다.