C++에서 주어진 n개의 범위에서 k번째로 작은 요소 찾기

이 문제에서는 n개의 범위(range)와 하나의 정수 k가 주어집니다. 우리의 목표는 주어진 n개의 범위에서 k번째로 작은 요소를 찾는 것입니다.

즉, 여러 개의 범위를 모두 합쳐 하나의 배열을 만든 뒤, 그 배열에서 k번째로 작은 값을 찾아야 합니다.

문제 이해를 위한 예시

입력: ranges = {{2, 5}, {7, 9}, {12, 15}}, k = 9

출력: 13

설명:

모든 범위를 합쳐 만들어진 배열은 다음과 같습니다.

{2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15}

이 배열에서 9번째(0부터 세었을 때)로 작은 요소는 13입니다.

해결 접근 방식

가장 간단한 방법은 모든 범위의 숫자를 하나의 배열에 차례대로 채워 넣는 것입니다. 각 범위는 연속된 정수로 구성되어 있으므로, 이렇게 만들어진 배열은 자동으로 오름차순으로 정렬됩니다. 따라서 배열을 완성한 후에는 단순히 k번째 위치의 값만 읽으면 답을 구할 수 있습니다.

다만 이 방법은 범위에 포함된 전체 숫자 개수를 S라고 할 때 O(S)의 시간과 공간이 필요합니다. 범위의 크기가 매우 큰 경우에는 각 범위별 요소 개수의 누적합을 계산한 뒤 이분 탐색으로 k번째 요소가 속한 범위를 찾는 최적화 기법을 활용하는 것이 효율적입니다.

솔루션 동작 예제 프로그램

#include <iostream>
using namespace std;

int main(){

    int arr[][2] = {{2, 5}, {7, 9}, {12, 15}};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 9;

    int rangeArr[1000];
    int size = 0;
    for(int i = 0; i < n; i++)
        for(int j = arr[i][0]; j <= arr[i][1]; j++) {
            rangeArr[size] = j;
            size++;
        }
    if(k < size)
        cout<<k<<"번째로 작은 요소는 "<<rangeArr[k]<<"입니다"<<endl;
    else
        cout<<"잘못된 인덱스입니다";
    return 0;
}

출력 결과

9번째로 작은 요소는 13입니다

위 코드에서는 2차원 배열 arr에 n개의 범위를 저장하고, 이중 반복문을 사용해 각 범위의 시작 값부터 끝 값까지를 rangeArr에 순서대로 삽입합니다. 범위가 연속적인 특성 덕분에 별도의 정렬 없이도 배열이 오름차순을 유지합니다.

이후 k가 배열의 유효 크기보다 작으면 rangeArr[k]를 출력하여 k번째로 작은 요소를 구하고, 그렇지 않으면 잘못된 인덱스임을 알려줍니다. 여기서 k는 0부터 시작하는 인덱스로 처리됩니다.