백준[10816] 숫자카드 2

아이디어

• 이분탐색을 사용할 줄 안다

접근방식

1. 들어온 요소들을 sort를 통해 오름차순으로 정렬해준다
2. 배열을 생성해, '같은 숫자의 가장 오른쪽 위치'에 숫자의 개수가 저장되게 끔 for문을 돌린다
3. 이분탐색을 통해 mid가 목표보다 작거나 같을 경우 mid +1 을 해준다(같은 숫자는 맞지만, 가장 오른쪽위치가 아닐 수 있기 때문)

#include <iostream>
#include <string.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <math.h>
#define ll long long
using namespace std;

ll arr[500001];

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

    vector<ll> v;
    int n; cin >> n;

    for(int i=0;i<n;i++)
    {
        ll num; cin >> num;
        v.push_back(num);
    }

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

    arr[0] = 1;

    ll now_num = v[0];
    ll now_cnt = 1;

    for(int i=1;i<n;i++)
    {
        if(now_num == v[i])
        {
            now_cnt++;
            arr[i] = now_cnt;
        }
        else
        {
            now_num = v[i];
            now_cnt=1;
            arr[i]=1;
        }
    }

    vector<ll> answer;

    ll m; cin >> m;
    while(m--)
    {
        ll target; cin >> target;

        ll temp_answer = 0;

        ll start = 0;
        ll end = n-1;

        while(start <= end)
        {
            ll mid = (start+end)/2;
            ll mid_number = v[mid];

            if(target >= mid_number)
            {
                if(target == mid_number) temp_answer = arr[mid];
                start = mid + 1;
            }
            else end = mid - 1;
        }
        answer.push_back(temp_answer);
    }

    for(ll num : answer) cout << num << " ";


    return 0;
}

평가

이분탐색을 알면 풀 수 있는 문제.
저는 조금 어려운 방식으로 풀었으나,
lower_bound, upper_bound를 사용하면 훨씬 쉽게 풀 수 있습니다.
아이디어는 알고 있었으나 lower_bound, upper_bound를 사용할 생각을 못하였습니다.

• 배울 것
  1) 이분탐색을 할 때 lower_bound, upper_bound 도 활용 하자