https://www.acmicpc.net/problem/10816
10816번: 숫자 카드 2
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,00
www.acmicpc.net
숫자 카드의 개수가 최대 500,000개이기 때문에 이분 탐색으로 해결해야 한다.
이분 탐색을 직접 구현해줘도 되지만 lower_bound와 upper_bound함수를 이용하여 쉽게 답을 구할 수 있다.
lower_bound : 찾으려는 값 이상이 처음 나타나는 위치를 반환한다.
upper_bound : 찾으려는 값을 처음으로 초과하는 위치를 반환한다.
upper_bound 값에서 lower_bound 값을 빼면 찾으려는 값의 개수를 구할 수 있다.
문제에 나와있는 예시를 이용하면 다음과 같은 숫자카드들을 먼저 정렬시킨다.
6 3 2 10 10 10 -10 -10 7 3
그럼 다음과 같이 정렬된다.
-10 -10 2 3 3 6 7 10 10 10
여기서 3의 개수를 찾기 위해 3의 lower_bound 값은 처음으로 3 이상이 나타나는 3번째 위치이고
upper_bound값은 처음으로 3을 초과하는 값(6)이 나타나는 5번째 위치이다.
upper_bound - lower_bound = 5 - 3 = 2로 개수를 구할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[500000];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i<n; i++) cin >> arr[i];
sort(arr, arr + n);
cin >> m;
int x;
while (m--) {
cin >> x;
int cnt = upper_bound(arr, arr + n, x) - lower_bound(arr, arr + n, x);
cout << cnt << ' ';
}
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2805. 나무 자르기 (0) | 2020.01.21 |
|---|---|
| [BOJ] 1654. 랜선 자르기 (0) | 2020.01.20 |
| [BOJ] 5567. 결혼식 (0) | 2019.11.13 |
| [BOJ] 7662. 이중 우선순위 큐 (0) | 2019.11.13 |
| [BOJ] 17472. 다리 만들기 2 (0) | 2019.10.16 |