Baekjoon 10816.숫자 카드 2 c++ [Silver IV]

unordered_map

메모리	시간
43828KB	488ms

#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

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

    int N;
    cin >> N;
    unordered_map<int, int> numbers;

    while (N--)
    {
        int i;
        cin >> i;
        numbers[i]++;
    }
    int M;
    cin >> M;
    while (M--)
    {
        int check;
        cin >> check;
        cout << numbers[check] << " ";
    }
    return 0;
}

 

이진탐색

메모리	시간
5936KB	288ms

 

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

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

    int N, M;
    cin >> N;

    vector<int> cards(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> cards[i];
    }

    sort(cards.begin(), cards.end());

    cin >> M;
    vector<int> queries(M);
    for (int i = 0; i < M; ++i)
    {
        cin >> queries[i];
    }

    for (int query : queries)
    {
        auto lower = lower_bound(cards.begin(), cards.end(), query);
        auto upper = upper_bound(cards.begin(), cards.end(), query);

        cout << (upper - lower) << " ";
    }

    return 0;
}

 

lower_bound는 10이 처음 등장하는 위치 찾기 -> 정렬된 배열에서 10은 인덱스 7에 처음 등장 -> 즉, lower_bound는 cards[7]을 가리킨다. -> upper_bound는 10보다 큰 값이 처음 등장하는 위치를 찾고 -> 정렬된 배열에서 10보다 큰 값은 없음 -> 따라서 upper_bound는 인덱스 10 (배열의 끝)을 가리킨다. upper - lower = 10 - 7 = 3