C++에서 숫자가 N개의 [L, R] 범위에 속하는지 확인하는 쿼리 프로그램

이 문제에서는 N개의 범위 [L, R]와 각각 숫자 val을 담고 있는 Q개의 쿼리가 주어집니다. 우리의 과제는 주어진 숫자가 N개의 범위 중 하나에 속하는지 확인하는 프로그램을 C++로 작성하는 것입니다.

문제 설명

L부터 R까지의 정수 값을 포함하는 [L, R] 형태의 N개의 범위가 주어집니다. 예를 들어, 범위 [3, 6]은 3, 4, 5, 6을 포함합니다. 각 쿼리마다 존재 여부를 확인할 값 val이 주어지며, val이 어떤 범위에라도 포함되어 있으면 true를, 어느 범위에도 속하지 않으면 false를 반환해야 합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력: ranges[N] = {{2, 4}, {6, 7}, {9, 12}}
Q = 3
Query = {1, 7, 10}

출력:
Not Present
Present
Present

설명

쿼리 1: 숫자 1은 어떤 범위에도 포함되어 있지 않습니다.

쿼리 2: 숫자 7은 범위 {6, 7}에 포함되어 있습니다.

쿼리 3: 숫자 10은 범위 {9, 12}에 포함되어 있습니다.

해결 접근 방식

val이 어떤 범위에 속하는지 확인하려면 모든 범위에 대해 해당 값을 검사해야 합니다. 이때 매번 모든 범위를 순회하는 대신, 해시맵(hashmap)과 이분 탐색(binary search)을 조합하면 효율적으로 문제를 해결할 수 있습니다.

동작 원리

먼저 모든 범위의 시작점(L)과 끝점(R)을 하나의 배열에 모아 정렬하고, 해시맵에는 해당 지점이 시작점인지(1) 끝점인지(2) 표시해 둡니다. 쿼리 값 val이 주어지면 lower_bound로 val보다 크거나 같은 첫 번째 지점을 찾습니다. 그 지점이 val과 정확히 일치하면 val은 범위의 경계값이므로 true를 반환하고, 일치하지 않으면서 그 지점이 끝점(R)이라면 val은 어떤 범위의 내부에 있는 것이므로 true를 반환합니다. 그 외의 경우에는 false를 반환합니다.

이 방법의 시간 복잡도는 전처리에 O(N log N), 각 쿼리 처리에 O(log N)으로, 단순 순회 방식의 O(N) 쿼리 처리보다 쿼리가 많은 경우 훨씬 유리합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
unordered_map<int, int> mpp;
void initialiseMap(int a[][2], int n){
    for (int i = 0; i < n; i++) {
        v.push_back(a[i][0]);
        mpp[a[i][0]] = 1;
        v.push_back(a[i][1]);
        mpp[a[i][1]] = 2;
    }
    sort(v.begin(), v.end());
}
bool isElementPresent(int val) {
    int ind = lower_bound(v.begin(), v.end(), val) - v.begin();
    if (v[ind] == val)
        return true;
    else {
        if (mpp[v[ind]] == 2)
            return true;
        else
            return false;
    }
}
int main(){
    int arr[][2] = {{2, 4}, {6,7}, {9, 12}};
    int n = 3;
    int Q = 3;
    int query[] = { 1, 7, 10 };
    initialiseMap(arr, n);
    for(int i = 0; i < Q; i++){
        cout<<"For Query "<<(i+1);
        if(isElementPresent(query[i]))
            cout<<": The given digit "<<query[i]<<" is present in one of the given ranges\n";
        else
            cout<<": The given digit "<<query[i]<<" is not present in any of the given ranges\n";
    }
    return 0;
}

실행 결과

For Query 1: The given digit 1 is not present in any of the given ranges
For Query 2: The given digit 7 is present in one of the given ranges
For Query 3: The given digit 10 is present in one of the given ranges