[26168] 배열 전체 탐색하기
난이도: Silver IV
체감 난이도: Silver IV + 0.3
태그
- Binary Search (이진 탐색)
- std::lower_bound, std::upper_bound, std::equal_range
- Sort (정렬)
풀이
1. 쿼리를 처리하기 전...
정렬이 되어있는 게 아무래도 데이터 처리에 편할 것으로 추정됩니다.
그러니 데이터를 정렬하고 시작해봅시다.
지금부터는 정렬된 데이터, 즉 \( 1 \le A_1 \le A_2 \le \cdots \le A_N \)을 가정합니다.
2. 1번 쿼리를 처리해보자.
특정 수 \( k \)보다 크거나 같은 값이 나오는 첫 위치를 \( i \)번째 위치라고 해봅시다.
즉, \( A_1 \le \cdots \le A_{i-1} < k \le A_i \le \cdots \le A_N \)이라고 합시다.
그럼, \( k \) 이상인 값들의 개수는 \( i \)번째부터 \( N \)번째까지, 총 \( N-i+1 \)개가 됩니다.
\( A \)를 정렬시켰으니, 이 위치는 이진 탐색으로 빠르게 찾아줄 수 있습니다.
또는, 정확하게 이 일을 해주는 std::lower_bound를 사용해줄 수도 있습니다.
3. 2번 쿼리를 처리해보자.
1번 쿼리와 비슷하게, 특정 수 \( k \)보다 큰 값이 나오는 첫 위치를 \( i \)번째 위치라고 해봅시다.
즉, \( A_1 \le \cdots \le A_{i-1} \le k < A_i \le \cdots \le A_N \)이라고 합시다. (부등호가 약간 달라졌어요!)
그럼, \( k \) 초과인 값들의 개수는 \( i \)번째부터 \( N \)번째까지, 총 \( N-i+1 \)개가 됩니다.
\( A \)를 정렬시켰으니, 이 위치 역시 이진 탐색으로 빠르게 찾아줄 수 있습니다.
또는, 정확하게 이 일을 해주는 std::upper_bound를 사용해줄 수도 있습니다.
4. 3번 쿼리를 처리해보자.
수 하나에 대해서는 잘 구했었는데, 두 수 \( s, e \) 사이에 있는 값의 개수는 어떻게 구해야 할까요?
위와 비슷하게, \( s \)와 \( e \)가 수열의 몇 번째 위치에 있는지 아는 게 좋을 것 같습니다.
그러니, 아래와 같은 위치를 찾았다고 생각해봅시다.
\( A_1 \le \cdots \le A_{i-1} < s \le A_i \le \cdots \le A_{j-1} \le e < A_j \le \cdots \le A_N \)
\( s \)의 위치는, 1번 쿼리에서 한 방식과 동일합니다.
\( e \)의 위치는, 2번 쿼리에서 한 방식과 동일합니다.
다르게 말하자면, 이 문제의 답은 upper_bound - lower_bound가 됩니다.
또는, 인덱스로 쓰자면 \( j - i \)개가 됩니다. (\( A_j \)가 범위 바깥임에 주의하세요!)
여담으로, 위 작업은 \( s = e \)라면 std::equal_range가 하는 일과 동일합니다.
코드
개인적으로는 아래와 같은 방식으로 생각하는 걸 좋아합니다.
- equal_range는 lower_bound와 upper_bound의 합작이다.
- equal_range = [lower_bound, upper_bound) = [begin, end) 구간이다.
- 그러므로 lower_bound는 특정 값 이상을, upper_bound는 특정 값 초과를 찾는다.
|
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
|
ll arr[100020];
void Main(){
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++){ cin >> arr[i]; }
sort(arr+1, arr+n+1);
while (q--){
int typ; cin >> typ;
if (typ == 1){
ll k; cin >> k;
auto idx = lower_bound(arr+1, arr+n+1, k) - arr;
cout << n+1 - idx << endl;
}
if (typ == 2){
ll k; cin >> k;
auto idx = upper_bound(arr+1, arr+n+1, k) - arr;
cout << n+1 - idx << endl;
}
if (typ == 3){
ll st, ed; cin >> st >> ed;
auto i1 = lower_bound(arr+1, arr+n+1, st) - arr;
auto i2 = upper_bound(arr+1, arr+n+1, ed) - arr;
cout << i2-i1 << endl;
}
}
}
|
cs |