C++로 구현하는 범위 조회 쿼리: 숫자가 N개의 L-R 범위 안에 속하는지 확인하기

이 문제에서는 n개의 범위(L, R)로 이루어진 2차원 배열 arr[][2]와 각각 정수 값을 담고 있는 Q개의 쿼리가 주어집니다. 우리의 목표는 각 쿼리의 숫자가 주어진 N개의 L-R 범위 중 하나에 속하는지 판별하는 프로그램을 작성하는 것입니다.

문제 설명

각 쿼리에 대해 해당 정수가 주어진 범위 중 적어도 하나에 포함되는지 확인해야 합니다. 만약 어느 하나의 범위에라도 속한다면 참(true)을 반환하고, 그렇지 않다면 거짓(false)을 반환합니다.

단, 주어진 범위들은 서로 겹치지 않는다는 조건이 있습니다.

예제로 문제 이해하기

입력

arr[n][2] = { {5, 7}, {1, 3}, {9, 12} }
n = 3
Q = 2, query = {10, 4}

출력

Yes
No

설명

첫 번째 쿼리 값 10은 범위 {9, 12}에 포함되므로 "Yes"이고, 두 번째 쿼리 값 4는 어떤 범위에도 속하지 않으므로 "No"입니다.

접근 방법

가장 단순한 해결 방법은 각 쿼리마다 모든 범위를 하나씩 검사하면서 해당 숫자가 포함되는 범위를 찾는 것입니다. 배열을 범위의 시작값 기준으로 미리 정렬해두면 탐색 효율을 높일 수 있습니다.

알고리즘

1단계 − 행렬을 행 단위로, 즉 범위의 시작값을 기준으로 정렬합니다.

2단계 − i를 0부터 Q까지 반복하며 모든 쿼리를 처리합니다.

2.1단계 − 요소가 어떤 범위에 속하는지 검사합니다. 즉, (arr[i][0] <= q && arr[i][1] >= q) 조건을 만족하면 true를 반환합니다.

솔루션 구현 예제

#include <iostream>
using namespace std;
bool isPresent(int arr[][2], int n, int element){
    for(int i = 0; i < n; i++){
       if(arr[i][0] <= element && arr[i][1] >= element)
          return true;
    }
    return false;
}
void solveQueries_Range(int arr[][2], int n, int Q, int query[]){
    int temp[2];
    // 범위 시작값 기준으로 버블 정렬
    for(int j = 0; j < (n - 1); j++){
       for(int k = (j + 1); k < n; k++)
          if(arr[j][0] > arr[k][0]){
             temp[0] = arr[k][0]; temp[1] = arr[k][1];
             arr[k][0] = arr[j][0]; arr[k][1] = arr[j][1];
             arr[j][0] = temp[0]; arr[j][1] = temp[1];
          }
    }
    for(int i = 0; i < Q; i++){
       if(isPresent(arr, n, query[i]))
          cout<<"For Query "<<(i + 1)<<": The number "<<query[i]<<" lies in the range\n";
       else
          cout<<"For Query "<<(i + 1)<<": The number "<<query[i]<<" does not lie in the range\n";
    }
}
int main(){
    int arr[][2] = { {5, 7}, {1, 3}, {9, 12} };
    int n = 3;
    int Q = 2;
    int query[] = { 10, 4 };
    solveQueries_Range(arr, n, Q, query);
    return 0;
}

출력 결과

For Query 1: The number 10 lies in the range
For Query 2: The number 4 does not lie in the range

시간 복잡도 분석

정렬에는 O(n²)(버블 정렬 기준) 또는 std::sort 사용 시 O(n log n)이 소요되며, 각 쿼리마다 모든 범위를 선형 탐색하므로 전체 시간 복잡도는 O(n × Q)입니다.

범위가 정렬되어 있고 서로 겹치지 않기 때문에, 각 쿼리에 대해 이진 탐색(binary search)을 활용하면 시간 복잡도를 O((n + Q) log n)으로 크게 개선할 수 있습니다. 쿼리 개수가 많은 경우 이 최적화를 적용하는 것이 좋습니다.