[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는 특정 값 초과를 찾는다.

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;
        }
    }
}