문제 소개
이 문제에서는 L~R 구간에 속한 정수들로 이루어진 N개의 범위가 range[N][2] 형태의 배열로 주어지고, 정수 k가 함께 제공됩니다. 우리의 목표는 이 N개의 범위로 생성된 수열에서 k번째 원소를 찾는 것입니다.
예제로 문제 이해하기
입력 : ranges[][] = {{1, 3}, {5, 7}}, k = 4
출력 : 5풀이 설명 −
생성되는 수열은 {1, 2, 3, 5, 6, 7}
여기서 네 번째 원소는 5입니다.방법 1: 단순 접근 – 전체 수열을 배열에 저장
가장 간단한 방법은 주어진 각 범위에 포함된 정수들을 하나의 배열에 순서대로 저장해 완전한 수열을 만든 뒤, 그 배열의 k번째 원소를 반환하는 것입니다.
구현 코드
#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
int rangeVal[10000];
int rangeSize = 0;
for(int i = 0; i < n; i++){
for(int j = range[i][0]; j <= range[i][1]; j++){
rangeVal[rangeSize] = j;
rangeSize++;
}
}
return rangeVal[k-1];
}
int main(){
int L[] = { 1, 5 };
int R[] = { 3, 8 };
int range[][2] = {{1, 3}, {5, 8}};
int n = sizeof(L) / sizeof(int);
int k = 4;
cout<<"범위로 생성된 수열의 "<<k<<"번째 원소는 "<<
findKthSmallestEleSeries(n, k, range);
return 0;
}
실행 결과
범위로 생성된 수열의 4번째 원소는 5
이 방법은 이해하기 쉽다는 장점이 있지만, 범위가 매우 넓은 경우 수열 전체를 저장해야 하므로 심각한 메모리 낭비나 오버플로 문제가 발생할 수 있습니다. 따라서 모든 원소를 저장하지 않고도 답을 구할 수 있는 더 효율적인 알고리즘이 필요합니다.
방법 2: 이진 탐색과 누적 카운트 배열 활용
더 효율적인 접근 방식은 이진 탐색(binary search)과 누적 카운트 배열을 조합하는 것입니다. 여기서 count[i]는 1번째부터 i번째 범위까지 포함된 정수의 총 개수를 의미합니다.
알고리즘은 다음 단계로 진행됩니다.
- 각 범위의 원소 개수를 누적하여 count 배열을 생성합니다.
- 이진 탐색을 통해 k번째 작은 값이 속하는 범위의 인덱스 i를 찾습니다.
- 그 범위 내에서 k번째 값의 상대적 위치(indexK)를 계산한 뒤, 해당 범위에서 이진 탐색으로 실제 값을 구합니다.
구현 코드
#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
int start = 1;
int end = n;
int count[n + 1];
count[0] = 0;
// i번째 범위까지의 누적 원소 개수 계산
for (int i = 0; i < n; i++)
count[i + 1] = count[i] + (range[i][1] - range[i][0]) + 1;
// k번째 값이 속한 범위를 이진 탐색으로 찾기
int index = -1;
int mid;
while (start <= end) {
mid = (start + end) / 2;
if (count[mid] > k) {
index = mid;
end = mid - 1;
}
else if (count[mid] < k)
start = mid + 1;
else {
index = mid;
break;
}
}
// 해당 범위 안에서 k번째 값 찾기
start = range[index - 1][0];
end = range[index - 1][1];
int indexK = k - count[index - 1];
while (start <= end) {
mid = (start + end) / 2;
if ((mid - range[index - 1][0]) + 1 == indexK) {
return mid;
}
else if ((mid - range[index - 1][0]) + 1 > indexK)
end = mid - 1;
else
start = mid + 1;
}
return -1;
}
int main(){
int L[] = { 1, 5 };
int R[] = { 3, 8 };
int range[][2] = {{1, 3}, {5, 8}};
int n = sizeof(L) / sizeof(int);
int k = 4;
cout<<"범위로 생성된 수열의 "<<k<<"번째 원소는 "<<
findKthSmallestEleSeries(n, k, range);
return 0;
}
실행 결과
범위로 생성된 수열의 4번째 원소는 5
복잡도 분석 및 추가 팁
방법 1은 시간·공간 복잡도가 모두 O(S)(S는 전체 원소 개수)로, 범위가 커질수록 비효율적입니다. 반면 방법 2는 누적 카운트 계산에 O(N), 이진 탐색에 O(log N)이 소요되므로 대규모 입력에서도 안정적으로 동작합니다.
참고로 각 범위는 연속된 정수 구간이므로, k번째 값이 속한 범위를 찾은 후에는 이진 탐색 없이 range[index-1][0] + indexK - 1 공식으로 즉시 계산할 수도 있습니다.