(백준 10816 c++) 숫자카드 2

문제

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

10816번: 숫자 카드 2

정답코드

#include <set>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n;
    int number1, number2;
    vector<int> arr1;

    for (int a = 0; a < n; a++)
    {
        cin >> number1;
        arr1.push_back(number1);
    }
    sort(arr1.begin(), arr1.end());
    cin >> m;
    for (int a = 0; a < m; a++)
    {
        cin >> number2;
        auto upper = upper_bound(arr1.begin(), arr1.end(), number2);
        auto lower = lower_bound(arr1.begin(), arr1.end(), number2);
        cout << upper - lower << " ";
    }
}

해설

처음에는 multiset에 count를 사용해서 해결하려고 했는데 틀렸다고 나와서 보니 시간복잡도가 O(n)이었음,

그리고 그냥 sort 하지않고 set을사용해서 자동으로 정렬하려고 했는데 그것도 오류남.

결국 백터를사용했고, upper lower_bound했는데, 이것도 시간초과남.

그래서 시간줄이는 방법으로 ios:: 저거 썼더니 패스.

ios::sync_with_stdio(false);
cin.tie(NULL);