백준 10816번 - 숫자 카드2 문제 C++ [이진 탐색], upper_bound()/lower_bound()

📍 백준 000번 - 제목 문제 프로그래밍 언어 

 

---

🧩문제 요약

<이진탐색>

제시된 크기 n만큼 수가 입력된다.

이후, 타겟값이 m개 주어질때 해당 타겟값이 배열에 몇개가 들어있는지를 순서대로 출력하라. 

 

 

 

---

🧾내가 작성한 초기 코드 

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

int input_card[500001], find_card[500001];

int countCard(const int num, int size){
    cout << "finding a same card...\n";
    // binary search로 타겟값 위치 찾기 
    int start = 0, end = size-1, mid = (start+end)/2;
    int cnt=0 ; 
    while(start <= end){
        cout << "start : " << start << ", end : " << end << ", mid : " << mid << ", mid_val : " << input_card[mid] <<"\n";
        if(num==input_card[mid]){
            cout << "We got same card. Now we are searching a another...\n";
            // 같은 카드가 있는지 탐색 
            for(int i=start; i<=end; i++){
                cout << "Is it the same ? " << num << ", " << input_card[i] << "\n";
                if(num==input_card[i]){
                    cnt++;
                }
                cout << "count : " << cnt << " \n";
            }
            return cnt;
            break;
        }else if(num < input_card[mid]){
            cout << "target num is smaller than mid--- " << num << " < " << input_card[mid] <<"\n";
            end = mid-1;
            mid = (start+end)/2;
        }else if(num > input_card[mid]){
            cout << "target num is bigger than mid--- " << num << " > " << input_card[mid] <<"\n";
            start = mid+1;
            mid = (start+end)/2;
        }
    }
    return 0;
}

int main(){
    int n,m,i; 
    cin >> n ;
    for(i=0; i<n; i++){
        cin >> input_card[i];
    }
    cin >> m ;
    for(i=0; i<m; i++){
        cin >> find_card[i];
    }
    sort(input_card, input_card+n);

    ////////
    cout << "checking sort...\n";
    for(i=0; i<n; i++){
        cout<< input_card[i];
    }
    cout << "\n";
    ////////
    for(i=0; i<m; i++){
        cout << "target num : " << find_card[i] << "\n";
        cout << countCard(find_card[i], n) << " ";
        cout << "\n";
    }
    cout << "\n";
}

cf) 영어문장은 그냥 틀려도 그러려니 봐주세여.. ㅎㅎ

---

 

👍이 문제에서 배운점

 

😕 문제점 1. 

초기 코드에서는 시간초과 문제가 발생한다.

아마도 이진 탐색 이후 같은 카드가 있는지 탐색하는 부분이 worst case가 O(n)이여서 그런것 같다. 

이진탐색으로 잘 구현해놓고 여기서 다시 선형탐색이 들어간다. 이부분을 어떻게 처리해야 할까 고민을 했다. 

 

 

✅ 이진 탐색을 이용한 std::upper_bound(), std::lower_bound() 

 

upper_bound(), lower_bound() 는 c++에서 이진탐색으로 원소를 탐색하는 함수이다. 

두 함수는 algorithm헤더에 들어있다. 

• lower_bound() : 찾으려는 key값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾음. 
• upper_bound() : 찾으려는 key값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾음.

두 함수의 사용방법은 다음과 같다. 

#include <algorithm>

int input_card[500001];
upper_bound(input_card, input_card+n, target_num);
lower_bound(input_card, input_card+n, target_num);

 

(배열의 시작, 배열의 끝 찾고자 하는 값)을 파라미터로 넣어주면 된다. 

이 두 함수의 return 값은 Iterator이기 때문에 실제 인덱스 값을 얻고 싶다면, return 값에서 배열 첫 번째 주소를 빼주면 된다. 

upper_bound(input_card, input_card+n, target_num) - input_card;
lower_bound(input_card, input_card+n, target_num) - input_card;

 

만약 찾고자 하는 값이 없다면 last(v.end())를 반환한다. 

이진 탐색을 기본으로 하기 때문에 O(logN)으로 탐색이 가능하다. 

 

lower_bound를 사용해 key값이 몇번째 인덱스에서 처음 나타나는지 찾고 upper_bound를 사용해 key값이 나타나는 마지막 인덱스를 찾아서 둘의 차를 구하면 key값이 해당 배열에 몇개 존재하는지 계산 할 수 있다. 

 

이렇게 완성된 코드는 다음과 같다. 

 

🧾완성된 코드 

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

int input_card[500001], find_card[500001];

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
	
    // 입력받기 
    int n,m,i; 
    cin >> n ;
    for(i=0; i<n; i++){
        cin >> input_card[i];
    }
    cin >> m ;
    for(i=0; i<m; i++){
        cin >> find_card[i];
    }
    sort(input_card, input_card+n); // 이진 탐색을 위한 정렬
	
    // upper_bound와 lower_bound를 사용한 target 값 갯수 세기 
    for(i=0; i<m; i++){
        cout << (upper_bound(input_card, input_card+n, find_card[i])-input_card ) - (lower_bound(input_card, input_card+n, find_card[i])- input_card) << " ";
    }
    cout << "\n";
}

---