[백준] 10816번: 숫자 카드 2 - C++

문제 출처:https://www.acmicpc.net/problem/10816

---

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

이 문제는 이진탐색 알고리즘을 약간 수정한 Lower bound, Upper bound 알고리즘을 써야 수월하게 풀이가 가능합니다.

Lower bound 란 찾고자 하는 값 이상이 처음 나타나는 위치 입니다.  

예를들어 정렬된 데이터 {1, 3, 4, 6, 6, 7, 8, 10} 에서 6이상인 값이 처음 나오는 위치는 3 입니다.

Lower bound 코드입니다.

int lower_binary(int*arr,int target,int size) {
    int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start){
        mid = (start + end) / 2;
        if (arr[mid] >= target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}

Upper bound 란 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치 입니다. 

예를들어 정렬된 데이터 {1, 3, 4, 6, 6, 7, 8, 10} 에서 6보다 큰 값이 처음 나오는 위치는 5 입니다.

Upper bound 코드입니다.

int upper_binary(int*arr, int target,int size) {
    int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start) {
        mid = (start + end) / 2;
        if (arr[mid] > target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}

위 글만 보고 눈치 채신분도 있겠지만 이 문제는 정렬된 숫자카드에서 상근이가 구해야 할 정수n 을 

Upper bound(n) - Lower bound(n) 을 하게되면 상근이가 숫자 카드를 몇개 가지고 있는지 알 수 있습니다. 

출처에 나와있는 예제로 설명해보면 

{6, 3, 2, 10, 10, 10, -10, 7, 3}의 숫자카드가 있습니다. 일단 Lower, Upper bound알고리즘은 기본적으로 이진탐색에서 응용하는 알고리즘이므로 이진탐색과 마찬가지로 배열이 정렬되어야 합니다. 

따라서 배열을 {-10, 2, 3, 3, 6, 7, 10, 10, 10}으로 정렬을 해줍니다. 이 배열 안에 숫자 10이 적힌 카드가 몇개인지 알고싶다면 

Upper bound(10) - Lower bound(10)을 하게 되면 Upper bound(10)은 9를 반환하고 Lower bound(10)은 6을 반환하기 때문에 9 - 6 = 3  이라는 결과를 쉽게 구할 수 있습니다.

단 한가지 주의해야 할 점은 배열{3} 에서 3의 갯수를 알고싶다고 했을때 위의 알고리즘을 쓰게되면 1이 아니라 0이 나오는 오류가 있습니다. 따라서 이 부분에 대하여 예외처리를 해주어야 합니다.

전체 코드입니다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
int lower_binary(int*arr,int target,int size) {
    int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start){
        mid = (start + end) / 2;
        if (arr[mid] >= target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}
 
int upper_binary(int*arr, int target,int size) {
    int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start) {
        mid = (start + end) / 2;
        if (arr[mid] > target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}
 
int main(void)
{
    int n, m, temp, target,lower,upper;
 
    scanf("%d", &n);
    int *m_arr = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &m_arr[i]);
    }
    sort(m_arr, m_arr + n);
    
    scanf("%d", &m);
    int *arr = new int[m];
    int *result = new int[m];
    for (int i = 0; i < m; i++) {
        scanf("%d", &arr[i]);
        result[i] = 0;
    }
 
    for (int i = 0; i < m; i++) {
        lower = lower_binary(m_arr, arr[i], n);
        upper = upper_binary(m_arr, arr[i], n);
        if (upper == n - 1 && m_arr[n - 1] == arr[i])
            upper++;
        result[i] = upper - lower;
    }
 
    for (int i = 0; i < m; i++) {
        printf("%d ", result[i]);
    }
    return 0;
}