[BaekJoon] 10816번 : 숫자카드 2

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• 이분탐색에서 찾아야 할 target 원소의 인덱스 중 가장 작은 값과 가장 큰 값을 찾아 빼는 값이 개수입니다.
• 직접 구현할 수 있지만, 헷갈릴 위험이 있기 때문에 STL 중 upper_bound와 lower_bound 값을 쓸 수 있습니다.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long arr[100000];
    int num;
    cin>>num;
    for(int i=0;i<num;i++){
        cin>>arr[i];
    }
    sort(arr, arr+num);

    int n;
    cin>>n;

    for(int i=0;i<n;i++){
        int ans;
        cin>>ans;

        bool check = false;
        long long s = 0;
        long long e = num-1;
        while(s<=e){
            long long mid = (s+e)/2;
            if(arr[mid] == ans){
                check = true;
                break;
            }else if(arr[mid]<ans){
                s = mid+1;
            }else{
                e = mid-1;
            }
        }
        cout<<check<<"\n";
    }

}

• upper_bound와 lower_bound는 배열은 포인터를 반환하고, STL은 iterator를 반환합니다.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<int> vec;
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++){
        int num;
        cin>>num;
        vec.push_back(num);
    }
    
    sort(vec.begin(), vec.end());
    
    int m;
    cin>>m;
    
    for(int i=0;i<m;i++){
        int num;
        cin>>num;
        
        vector<int>::iterator left = lower_bound(vec.begin(), vec.end(), num);
        vector<int>::iterator right = upper_bound(vec.begin(), vec.end(), num);
        cout<<right-left<<"\n";
    }
}

 

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.