BOJ 10816. 숫자카드 2

문제

코드

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

using namespace std;

int main(int argc, char const *argv[])
{

    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m, aNum, bNum;
    cin >> n;
    vector<int> a;
    vector<int> b;
    for (int i = 0; i < n; i++)
    {
        cin >> aNum;
        a.push_back(aNum);
    }
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> bNum;
        b.push_back(bNum);
    }
    sort(a.begin(), a.end());

    for (int i = 0; i < b.size(); i++)
    {
        int cnt = 0;
        int temp = b[i];

        int left = 0;
        int right = a.size() - 1;

        while (left <= right)
        {
            int mid = (left + right) / 2;

            if (a[mid] == temp)
            {

                cnt++;
                if (a[mid + 1] != temp)
                {
                    right = mid - 1;
                    continue;
                }
                else
                {
                    left = mid + 1;
                    continue;
                }
            }
            else if (a[mid] < temp)
            {
                left = mid + 1;
            }
            else if (a[mid] > temp)
            {
                right = mid - 1;
            }
        }
        b[i] = cnt;
    }

    for (int i = 0; i < b.size(); i++)
    {
        cout << b[i] << ' ';
    }

    return 0;
}

• 숫자가 매우 크기 때문에, BF처럼 하면 시간초과가 날 것이라고 생각해 이분탐색으로 접근하기로 했다.
• 이분탐색으로 원하는 값들을 찾아내는 것은 성공했다.
• 하지만 , 원하는 값들이 하나 이상일 경우에 문제가 생겼는데, 이때, 같은 값들이 오른쪽에 없으면
  검색을 왼쪽방향으로 진행하는 방식으로 시도했다. 같을때마다 cnt++수를 증가시키는 방식
• 또 문제!!!는 양옆에 같은 숫자가 존재할 경우에 어떻게 처리해야 할지 너무 복잡해졌다.
• 이때, 숫자가 처음 나오는 시작 인덱스 ~ 마지막으로 나오는 인덱스의 수를 합하면 카드의 수가 나오게 된다.
• 이를 쉽게 할 수 있는 메서드가 lower_bound , upper_bound

코드2

헤더파일 : <algorithm>
STL라이브러리 lower_bound , upper_bound 사용

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

using namespace std;

int main(int argc, char const *argv[])
{

    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m, aNum, bNum, target;
    cin >> n;
    vector<int> a;

    vector<int>::iterator lower;
    vector<int>::iterator upper;
    for (int i = 0; i < n; i++)
    {
        cin >> aNum;
        a.push_back(aNum);
    }
    sort(a.begin(), a.end());
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> target;
        upper = upper_bound(a.begin(), a.end(), target);
        lower = lower_bound(a.begin(), a.end(), target);

        cout << upper - lower << ' ';
    }

    cout << '\n';
    return 0;
}

lower_bound : 해당 숫자가 처음 나오는 위치
upper_bound : 해당 숫자가 끝나는 위치

코드 3

함수로 구현한 코드

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

using namespace std;

int lower_binary(vector<int> v, int target, int size)
{
    int mid;
    int left = 0, right = size - 1;
    while (right > left)
    {
        mid = (left + right) / 2;
        if (v[mid] >= target)
            right = mid;
        else
            left = mid + 1;
    }

    return right;
}
int upper_binary(vector<int> v, int target, int size)
{
    int mid;
    int left = 0, right = size - 1;
    while (right > left)
    {
        mid = (left + right) / 2;
        if (v[mid] > target)
            right = mid;
        else
            left = mid + 1;
    }

    return right;
}
int main(int argc, char const *argv[])
{

    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m, aNum, bNum, lower, upper;
    cin >> n;
    vector<int> a;
    vector<int> b;
    for (int i = 0; i < n; i++)
    {
        cin >> aNum;
        a.push_back(aNum);
    }
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> bNum;
        b.push_back(bNum);
    }
    sort(a.begin(), a.end());

    for (int i = 0; i < b.size(); i++)
    {
        lower = lower_binary(a, b[i], n);
        upper = upper_binary(a, b[i], n);
        if (upper == n - 1 && a[n - 1] == b[i])
            upper++;

        b[i] = upper - lower;
    }

    for (int i = 0; i < m; i++)
    {
        cout << b[i] << '\n';
    }

    return 0;
}