백준 10816 ( C++ )

숫자 카드 2

 

이분 탐색의 upper bound와 lower bound를 이용하여 푸는 문제이다.

 

 

upper bound 와 lower bound 란?

 

이분 탐색으로 배열에서 숫자를 탐색할 때 찾으려는 숫자의 개수가 배열에서 여러 개 존재할 수 있다.

이때 탐색된 동일한 숫자들중 가장 작은 인덱스 값이 lower bound, 가장 큰 인덱스 값이 upper bound이다.

 

예로 길이가 10이고 각 원소 값이 { 1 , 3, 5, 9 , 11 , 13 ,19 , 19 , 19 , 20 } 인 배열에서 19를 찾는다고 해보자.

19가 가장 처음 나온 인덱스는 6 , 가장 나중에 나온 인덱스는 8 이므로 lower bound는 6, upper bound는 8이 된다.

 

이를 이용하여 문제를 해결해야 시간 초과가 발생하지 않는다.

 

 

Lower bound와 Upper bound 찾는 코드

 

보통의 이분 탐색 (binary search ) 코드에서 살짝 변형만 해주면 된다.

 

 

 

lower bound를 찾는 코드

 

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

 

 

 

upper bound 를 찾는 코드

 

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

 

그래서 정답은 upper bound - lower bound를 출력하면 된다.

 

단, 위 코드를 이용하면 upper bound와 lower bound 가 같은 경우, 예로 {3}인 배열에서 3을 찾는 경우에는 0을 출력해버리므로 예외처리를 해주어야 한다.

 

 

 

코드

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int lower_binary(int* arr, int target, int size) {
    int mid, start, end;
 
    start = 0, end = size - 1;
    
    while (start < end) {
        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 (start < end) {
        mid = (start + end) / 2;
        if (arr[mid] > target)
            end = mid;
        else
            start = mid + 1;
    }
    return end;
}
 
int main(void) {
 
    int N;
    cin >> N;
    
    int* arr = (int*)malloc(sizeof(int) * N);
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + N);
    
    int M;
    cin >> M;
 
    int* numToFind = (int*)malloc(sizeof(int) * M);
    
 
    for (int i = 0; i < M; i++) 
        cin >> numToFind[i];
        
 
    for (int i = 0; i < M; i++) {
        int lower = lower_binary(arr, numToFind[i], N);
        int upper = upper_binary(arr, numToFind[i], N);
 
        if (upper == N - 1 && arr[N - 1] == numToFind[i])
            upper++;
 
        cout << upper - lower << " ";
    }
 
    free(arr);
    free(numToFind);
 
}
 

 

 

 

결과