[이분탐색] BOJ 10816번 숫자 카드2 - 오답노트

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

10816번: 숫자 카드 2

- 문제파악

배열에는 중복 가능한 N개의 요소가 주어진다. 그 이후에 입력되는 숫자들이 배열에 몇개가 있는지 출력하라.

 

- 나의 접근

배열에서 찾고싶은 정수가 있다면 처음 나타는 인덱스와 마지막에 나타나는 인덱스를 빼면 된다는 발상까지는 성공했으나 구현이 쉽지 않았다.

 

그런데 STL에 함수가 있었다...

 

이분탐색 힘들게 구현하지 말고 STL을 활용하자...

 

- 정답

STL 에 있는 upper_bound 함수는 정렬된 배열내에서 가장 첫번째에 위치한 인자로 입력된 값의 위치를 반환한다.

lower_bound 함수는 반대로 정렬된 배열내에서 가장 마지막에 위치한 인자로 입련된 값의 위치를 반환다.

 

#include "bits/stdc++.h"
using namespace std;

int arr[500005];
int n;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);
    int m;
    cin >> m;
    while (m--) 
    {
        int t;
        cin >> t;
        cout << upper_bound(arr, arr + n, t) - lower_bound(arr, arr + n, t) << ' ';
    }
}