[백준 10816번] [이분 탐색] [bound function] 숫자 카드 2

이 문제에 대해서는 접근하는 방법이 여러가지가 있다.

 

1. 이분탐색으로 접근하는 방법

숫자가 상당히 큰 것을 보고, 이분탐색을 활용하여 시간을 줄여서 숫자카드에 존재하는 숫자를 탐색해주면 된다고 파악하면 된다.

 

이 문제의 경우에는, 이분탐색을 정확하게 접근해야 하는데, 결과적으로 나오는 index의 값이 upper_bound와 lower_bound로 나뉜다.

이분탐색으로 접근하기 위해서는, 데이터가 연속적으로 이어져있어야 하기때문에 반드시 sorting을 하고 나서 진행해야 한다.

 

일반적으로 중복되는 수가 없는 경우 중간값이 compare하는 값보다 작을 때는, start부터 mid값까지의 값은 compare하는 값보다 무조건 작을 수 밖에 없으므로 판단해야하는 범위는 (mid + 1, end)로 이동하게 된다.

반면에, compare하는 값보다 클 때는, mid부터 end까지의 값은 compare하는 값보다 무조건 클 수 밖에 없으므로 판단해야하는 범위는 (start, mid -1)로 이동하게 된다. 만약, compare한 값과 같을때는 그 값을 출력하면 된다.

 

그런데 중복되는 수가 존재하는 경우에는 이분탐색을 설정하는 방법에 따라서 출력되는 방법이 달라지게 된다.

설정하는 방법은 총 2가지가 존재하는데, Upper_bound와 Lower_bound이다.

 

1.Upper_bound

위 방식은 compare할 숫자를 기준으로 자기보다 큰 최소의 값을 가지는 index를 출력시킨다.
중간값이 compare_value와 작은 경우에는 당연하게 start를 mid + 1로 옮기지만, 같은 값이 나와도 mid + 1로 옮김으로써 , 수렴값을 compare_value를 가지는 최대 index에서 1칸보다 큰 값으로 수렴시킨다.

즉, 결과적으로 마지막 compare_value를 가지는 값의 다음 값까지 start지점이 옮겨지게 되고, 결과적으로 start값과 end는 같아진다.
왜냐하면, 중간값이 compare_value보다 작거나 같은 순간 계속해서 판단하는 scope가 한칸씩 뒤로 밀린다. 더 큰 경우에는 계속해서 scope가 앞쪽으로 좁아지게 된다. 에초에 mid값은 계속해서 작아지게 되기에 end값이 계속해서 앞쪽으로 밀리기 때문이다. 그래서 굳이 mid - 1로 하지 않아도 무방하다.

다만, end값을 반드시 초기 vector의 크기로 해야한다.
왜냐하면 끝의 값이 compare_value인 경우에는 마지막 index가 튀어나오게 되어 예외케이스가 발생하기 때문이다.

// Upper_bound (이분탐색에서의 상계를 구하는 방법)

int start = 0;
int end = vector_container.size();

while (start < end){
    mid = (start + end) / 2;
    
    if(card[mid] <= compare_value){
        start = mid + 1;
    }
    
    else{
        end = mid;
    }
}

2.Lower_bound

위 방식은 Upper_bound와 기본적으로 방법은 거의 유사하나, compare할 숫자를 기준으로 compare와 같은 수를 갖는 index의 최댓값을 출력시킨다.
중간값이 compare_value와 크거나 같은 경우에는 end를 mid로 옮김으로써 scope는 뒤쪽부분이 앞쪽으로 좁아지게 된다. 작은 경우에는 start가 mid + 1로 옮김으로써 scope가 한칸씩 앞으로 이동하게 된다. 따라서 결과적으로 수렴값을 compare_value를 가지는 index의 최솟값으로 수렴시킨다.

즉, 결과적으로 마지막 compare_value를 가지는 값의 최초의 값으로  start지점이 옮겨지게 되고, 결과적으로 start값과 end는 같아진다.
왜냐하면, 중간값이 compare_value보다 작으면 계속해서 판단하는 scope가 한칸씩 뒤로 밀린다. 더 크거나 같은 경우에는 계속해서 scope가 앞쪽으로 좁아지게 된다. 에초에 mid값은 계속해서 작아지게 되기에 end값이 계속해서 앞쪽으로 밀리기 때문이다. 그래서 굳이 mid - 1로 하지 않아도 무방하다.

이 경우에는 반드시 end값을 반드시 초기 vector의 크기로 해야하는 것은 아니지만 일관성을 위해서 vector의 크기로 end를 잡는 것이 좋다.

// Lower_bound (이분탐색에서의 하계를 구하는 방법)

int start = 0;
int end = vector_container.size();

while (start < end){
    mid = (start + end) / 2;
    
    if(card[mid] < compare_value){
        start = mid + 1;
    }
    
    else{
        end = mid;
    }
}

위의 방식을 활용하여 코드를 구현하면 다음과 같다. 그런데 이 문제에서 입출력이 50만으로 되게 많은 편으로 추가적으로 빠른 입출력 코드를 입력해야 시간초과가 나지 않는다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

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

    int n;
    cin >> n;
    vector<int> card;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        card.push_back(temp);
    } // store data

    sort(card.begin(), card.end()); // sorting data

    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        int check_value;
        cin >> check_value;
        int start = 0;
        int end = n;
        int mid = -1;
        int min, max;

        // Upper bound
        while (start < end){
            mid = (start + end) / 2;
            if(card[mid] <= check_value){
                start = mid + 1;
            }
            else{
                end = mid;
            }
        }

        max = start;

        start = 0;
        end = n;

        // Lower bound
        while (start < end){
            mid = (start + end) / 2;
            if(card[mid] < check_value){
                start = mid + 1;
            }
            else{
                end = mid;
            }
        }
        min = start;

        cout << max - min<< " ";
    }
    
    cout << "\n";

    return 0;

}

 

2. 각 숫자들에 해당하는 배열을 미리 세팅하는 방법

이 방법은 숫자들에 해당하는 배열을 미리 잡아두고, 해당하는 배열에 숫자를 집어넣으면 된다.

근데, 이 문제에서는 숫자의 최솟값이 -10000000이므로 해당 숫자 + 10000000하면 인덱스와 숫자를 각각 매칭시킬 수 있다.

 

위의 방식을 활용하여 코드를 작성하면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

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

    int n;
    cin >> n;

    vector<int> card(20000001, 0);

    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        temp += 10000000;
        card[temp] += 1;
    } //data sort

    int m;
    cin >> m;

    for(int i = 0; i < m; i++){
        int temp;
        cin >> temp;
        temp += 10000000;
        cout << card[temp] << " ";
    }

    cout << "\n";
    return 0;
}

다만, 이 방식으로 하면 이분 탐색으로 하는 것보다 메모리에서 손실이 많이나게 된다.

실제로 백준에서 구동한 결과는 다음과 같다.

시간적인 측면에서는 크게 차이가 나지 않지만, 메모리 측면에서는 엄청나게 차이가 난다는 것을 볼 수 있다.

 

3. Upper_bound / Lower_bound 함수를 이용하는 방법

첫번째 방법으로 이용한 방법을 구현하지 않아도, 이용할 수 있는 함수가 존재한다.

사용방법은 다음과 같다.

 

1. upper_bound
upper_bound(v.begin(), v,end(), compare_value)

2.lower_bound
lower_bound(v.begin(), v.end(), compare_value)

위 함수의 Return 값은 iterator이므로 해당하는 index를 긁어오기 위해서는 v.begin()을 빼주어야 한다.
나오는 값 자체는 이분탐색의 결과와 동일하다.

위의 방식을 활용하여 코드를 작성하면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

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

    int n;
    cin >> n;

    vector<int> card;

    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        card.push_back(temp);
    } //data sort

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

    int m;
    cin >> m;

    for(int i = 0; i < m; i++){
        int temp;
        cin >> temp;
        int upper, lower;
        upper = upper_bound(card.begin(),card.end(),temp) - card.begin();
        lower = lower_bound(card.begin(),card.end(),temp) - card.begin();
        cout << upper - lower << " ";
    }

    cout << "\n";
    return 0;
}

위의 방식들을 활용하여, 코드를 직접 백준에서 돌려본 결과는 다음과 같다.

 

아래에서부터 1번부터 3번으로 이어진다.