[BOJ알고리즘, C++]#10816_숫자 카드2, lower_bound, upper_bound

 

[BOJ 알고리즘, C++] #10816_숫자 카드 2, lower_bound, upper_bound

 

BOJ 알고리즘 문제 풀이, 10816_숫자 카드2

정렬 알고리즘을 통해 주어진 숫자 카드가 존재하는지 탐색합니다.

 

 

---

 

문제

 

풀이

1. Map 컨테이너 활용

// 1. Map 컨테이너를 활용했지만, 2번 코드보다 소요 시간과 메모리 사용량이 비교적 훨씬 높음...

#include <iostream>
#include <map>
#include <algorithm>
typedef long long ll;
using namespace std;

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

    int N, M;
    // 숫자 + 개수
    map<ll, int> m;
    vector<ll> v;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        ll num;
        cin >> num;

        m[num]++;
    }

    cin >> M;

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

        v.push_back(m[num2]);
    }

    for (int val : v)
        cout << val << " ";
}

1. Map 컨테이너 활용

먼저, 입력받은 숫자 카드와 각 숫자 카드의 개수를 한 쌍으로 Map 컨테이너에 삽입합니다.

2. v.push_back(m [num2])

입력받은 M개의 숫자 카드를 "Key"로 "Value" 값을 벡터에 순서대로 삽입합니다. 이때, Map 컨테이너에 존재하지 않는 새로운 숫자 카드, 혹은 "Key"값을 반환하면 0이 반환되는 것을 이용합니다.

* 수행 속도와 메모리 사용량이 너무 높아서 새로운 방법을 생각해보았습니다.

 

2. 정렬 알고리즘 및 lower_bound + upper_bound 활용

// 2. Sort 알고리즘과 lower_bound와 upper_bound 활용 코드, 시간 + 성능 모두 훨씬 뛰어남

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;

using namespace std;

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

    int N, M;
    vector<ll> v;
    vector<int> v2;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        ll num;
        cin >> num;

        v.push_back(num);
    }

    sort(begin(v), end(v));

    cin >> M;

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

        auto upper = upper_bound(begin(v), end(v), num2);
        auto lower = lower_bound(begin(v), end(v), num2);

        v2.push_back(upper - lower);
    }

    for (auto val : v2)
        cout << val << " ";
}

1. lower_bound + upper_bound

같은 수의 lower_bound와 upper_bound를 구해서 빼주면 해당 숫자의 개수를 얻을 수 있습니다. 주의할 점은 lower_bound와 upper_bound 알고리즘을 사용하기 위해선 정렬이 선행되어야 합니다!