백준 10816번 - 숫자카드2(C++/병합 정렬/ Merge Sort/ 이분 탐색)

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

 

접근법

숫자카드1과 비슷한 문제였다. 숫자카드 1은 숫자의 존재여부를 물어봤다면 여기선 숫자의 개수를 물어보았다.

algorithm 헤더파일에 있는 std::sort, std::upper_bound, std::lower_bound 를 이용하면 쉽게 풀 수 있지만, 여기선 다 구현해 보기로 한다.

 

MergeSort는 그동안 너무 많이 풀어봤으므로 일단 생략한다.

upper_bound, lower_bound 는 이진 탐색의 while문의 등호만 다르게 해주면 된다. 간단히 생각해서 중간 값과 비교를 할때 등호를 포함해서 비교해주면, 만약 같은 값이어도 범위를 좁힐것 이므로, lower에 사용한다.

 

중간값과 비교할때 등호를 포함하지 않으면 start를 뒤로 당겨서 탐색 범위를 뒤로 나아가므로, 찾으려는 마지막값 Idx 에서 +1 된 값이 나올것이다.

 

우리는 범위를 N까지 제한하므로 끝값을 구할때는 N+1 값이 아닌  N값이 나온다는것을 유의해야한다. 즉 마지막 값일때만 해당 upper idx에  ++해주면 끝난다.

코드

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

int nums[500000] = { 0, };
int find[500000] = { 0, };

void merge(int start, int mid, int end)
{
    int startIdx = start;
    int midIdx = mid + 1;
    vector<int> tmp;
    while (startIdx <= mid && midIdx <= end)
    {
        if (nums[startIdx] >= nums[midIdx])
        {
            tmp.push_back(nums[midIdx]);
            midIdx++;
        }
        else {
            tmp.push_back(nums[startIdx]);
            startIdx++;
        }
    }

    if (startIdx <= mid)
    {
        while (startIdx <= mid)
        {
            tmp.push_back(nums[startIdx]);
            startIdx++;
        }
    }
    else {
        while (midIdx <= end)
        {
            tmp.push_back(nums[midIdx]);
            midIdx++;
        }
    }
    for (int i = 0; i < tmp.size(); i++)
    {
        nums[start + i] = tmp[i];
    }
}

void MergeSort(int start, int end)
{
    if (start >= end) return;
    int mid = (start + end) / 2;

    MergeSort(start, mid);
    MergeSort(mid + 1, end);
    merge(start, mid, end);
}

int lower(int start, int end, int target)
{

    while (start < end)
    {
        int mid = (start + end) / 2;
        if (nums[mid] >= target)
        {
            end = mid;
        }
        else
        {
            start = mid + 1;
        }
    }
    return end;
}

int higher(int start, int end, int target)
{

    while (start < end)
    {
        int mid = (start + end) / 2;
        if (nums[mid] > target)
        {
            end = mid;
        }
        else
        {
            start = mid + 1;
        }
    }
    return end;
}

int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        nums[i] = num;
    }
    MergeSort(0, N-1);
    int M; 
    cin >> M;
    vector<int> result(M);
    for (int i = 0; i < M; i++)
    {
        int num;
        cin >> num;
        int low = lower(0, N - 1, num);
        int high = higher(0, N - 1, num);
        if (high == N - 1 && nums[N - 1] == num)
            high++;
        result[i] = high - low;
    }
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << " ";

}