Written by JS970
on February 6, 2023

10816 - 숫자 카드 2

난이도: 실버 4
날짜: 2023년 2월 6일
상태: Correct/Retry
추가 검토 여부: Yes

solution

algorithm헤더의 lower_bound, upper_bound함수를 사용해야 하는 문제였다.
- 이진탐색으로 원소를 탬색하는 알고리즘이다. 직접 이진탐색을 통해 구현하려 했으나… 실패했다.
map자료구조 사용하여 해결할 수도 있다.(시도해볼 것)
M에 대한 배열을 구현하지 않고 입력받는 즉시 연산하여 출력하는 방식으로 구현할 수도 있다.

code

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

bool comp(pair<int, int> a, pair<int, int> b)
{
    return a.second < b.second;
}

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

    int N;
    cin >> N;
    int * arrN = new int[N];
    int elem;
    for(int i = 0; i < N; i++)
        cin >> arrN[i];
    sort(arrN, arrN + N);

    int M;
    cin >> M;
    pair<int, int> * arrM = new pair<int, int>[M];
    int * ans = new int[M];
    for(int i = 0; i < M; i++)
    {
        cin >> arrM[i].first;
        arrM[i].second = i;
    }
    sort(arrM, arrM + M);

    int first, last;
    for(int i = 0; i < M; i++)
    {
        first = lower_bound(arrN, arrN + N, arrM[i].first) - arrN;
        last = upper_bound(arrN, arrN + N, arrM[i].first) - arrN;
        arrM[i].first = last - first;
    }
    sort(arrM, arrM + M, comp);
    for(int i = 0; i < M; i++)
        cout << arrM[i].first << " ";
    cout << endl;

    return 0;
}

ref

10816번: 숫자 카드 2

Top