C++에서 주어진 값을 포함하는 구간의 개수 구하기

여러 개의 구간(interval)이 담긴 2차원 배열 arr[][]와 하나의 숫자 value가 주어졌다고 가정해 봅시다. 이때 우리의 목표는 value가 속해 있는 구간이 총 몇 개인지 찾아내는 것입니다.

예를 들어 구간이 [ [1,5], [3,7] ]이고 value가 4라면, 4는 두 구간 모두에 포함되므로 결과는 2가 됩니다.

입력/출력 예시

예시 1

입력:

arr[4][2] = { { 1, 20 }, { 12, 25 }, { 32, 40 }, { 15, 18 } }, value = 16

출력:

주어진 값이 포함된 구간의 개수: 3

설명: 값 16은 1~20, 12~25, 15~18 세 구간에 모두 포함됩니다.

예시 2

입력:

arr[4][2] = { { 1, 20 }, { 20, 30 }, { 30, 40 }, { 40, 50 } }, value = 60

출력:

주어진 값이 포함된 구간의 개수: 0

설명: 값 60은 arr[][]에 있는 어떤 구간의 최대 범위보다도 크기 때문에 어느 구간에도 포함되지 않습니다.

접근 방법

모든 구간을 일일이 순회하며 값을 비교하는 대신, 주파수(누적) 배열을 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

각 구간의 시작점에서 +1, 끝점 바로 다음 위치에서 −1을 기록합니다(차분 배열 기법).
이후 배열을 순회하며 앞 요소의 값을 더해 누적합을 만들면, 각 인덱스 i에는 i를 포함하는 구간의 개수가 저장됩니다.
최종적으로 arr_2[value]를 반환하면 value가 속한 구간의 개수를 알 수 있습니다.

알고리즘 단계

구간이 담긴 정수형 2차원 배열 arr[][]와 정수 value를 입력받습니다.
함수 intervals_values(int arr[][2], int size, int value)는 arr와 value를 받아 value가 속한 구간의 개수를 반환합니다.
주파수 배열 arr_2[]를 선언하고 0으로 초기화합니다.
low는 INT_MAX로, highest는 INT_MIN으로 초기화하여 구간의 최솟값과 최댓값을 추적합니다.
for 반복문으로 i=0부터 i<size까지 arr[][]를 순회하면서, 각 구간의 왼쪽 끝 temp에 대해 arr_2[temp]를 증가시키고, 오른쪽 끝 temp_2에 대해 arr_2[temp_2+1]을 감소시킵니다.
순회 중 temp < low라면 low를, temp_2 > highest라면 highest를 갱신합니다.
low부터 highest까지 순회하며 arr_2[i] = arr_2[i] + arr_2[i−1]로 누적합을 계산합니다.
마지막으로 arr_2[value]를 결과로 반환합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
#define max 1000

int intervals_values(int arr[][2], int size, int value){
    int arr_2[max] = {0};          // 주파수 배열 초기화
    int low = INT_MAX;
    int highest = INT_MIN;

    for(int i = 0; i < size; i++){
        int temp = arr[i][0];      // 구간의 시작점
        arr_2[temp] = arr_2[temp] + 1;
        int temp_2 = arr[i][1];    // 구간의 끝점
        arr_2[temp_2 + 1] = arr_2[temp_2 + 1] - 1;

        if(temp < low){
            low = temp;
        }
        if(temp_2 > highest){
            highest = temp_2;
        }
    }
    // 누적합 계산: 각 인덱스에 해당 값을 포함하는 구간의 개수가 저장됨
    for(int i = low + 1; i <= highest; i++){
        arr_2[i] = arr_2[i] + arr_2[i - 1];
    }
    return arr_2[value];
}

int main(){
    int arr[4][2] = { { 3, 20 }, { 2, 13 }, { 25, 30 }, { 15, 40 } };
    int size = sizeof(arr) / sizeof(arr[0]);
    int value = 28;

    cout << "주어진 값이 포함된 구간의 개수: "
         << intervals_values(arr, size, value);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻습니다.

주어진 값이 포함된 구간의 개수: 2

설명: 값 28은 [25, 30]과 [15, 40] 두 구간에 포함되므로 결과는 2입니다.

마무리

이 접근법은 단순히 모든 구간을 매번 검사하는 O(N × M) 방식과 달리, 전처리 후 상수 시간(O(1))에 임의의 값이 속한 구간 개수를 조회할 수 있다는 장점이 있습니다. 다만 좌표 범위가 크다면 맵(map)이나 좌표 압축 등을 함께 사용해 메모리 사용량을 줄이는 것이 좋습니다.