백준 10816 C++

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

생각
1. 배열 세 개 만들어서 두 개는 입력받고 한 개는 몇 개 가지고 있는지 계산해서 출력
2. 쉽긴 한데 배운 걸 써먹어 보자면! 비교를 할 때 정렬 후 이분탐색으로 비교하면 시간이 더 줄어들 것 같으니 이 걸 써보자! 정렬은 상근이가 가지고 있는 숫자카드를 정렬하면 될 듯

 

정답 코드

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

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

    sort(arr1, arr1+n);
    for (int i = 0; i < m; i++) {
        int cnt = upper_bound(arr1, arr1+n, arr2[i]) - lower_bound(arr1, arr1+n, arr2[i]);
        //두 위치의 차이가 arr2[i]의 등장 횟수!
        cout << cnt << " ";
    }
}

 

문제를 풀다가 발견한 건데...

이분탐색의 low와 high가 이미 구현되어 있더라고?? 세상 참 편하다

upper_bound / lower_bound를 반복문에 넣고 두 번째 배열의 인덱스도 같이 돌려주면!! 금방 끝남!

근데 크거나 같은 위치를 반환하니까 다른 문제에서는 이분탐색 구현이 더 나을지도 모르겠다