두 개의 정수 L과 R로 표현되는 N개의 구간이 주어졌다고 가정해 보겠습니다. 이때 나머지 N-1개 구간을 모두 포함(덮는)하는 하나의 구간이 존재하는지 확인하고, 존재한다면 해당 구간의 0 기반 인덱스를 찾아야 합니다. 만약 그러한 구간이 없다면 -1을 출력하면 됩니다.
예를 들어 L = [2, 4, 3, 1], R = [4, 6, 7, 9]라고 할 때 출력은 3입니다. 이는 인덱스 3에 있는 구간 [1, 9]가 나머지 N-1개 구간의 모든 요소를 포함한다는 의미입니다.
접근 방법
모든 L과 R의 값이 서로 다르다는 조건이 주어져 있으므로 문제는 아주 간단하게 해결할 수 있습니다. 가장 작은 L값을 가지는 구간과 가장 큰 R값을 가지는 구간을 각각 찾은 후, 두 값이 동일한 구간에서 나왔다면 다른 모든 구간이 그 구간 내부에 속한다는 뜻입니다. 반대로 서로 다른 구간이라면 조건을 만족하는 구간은 존재하지 않습니다.
알고리즘의 단계는 다음과 같습니다.
- 배열을 순회하며 최소 L값을 가지는 구간의 인덱스(minIdx)를 찾습니다.
- 같은 방식으로 최대 R값을 가지는 구간의 인덱스(maxIdx)를 찾습니다.
- minIdx와 maxIdx가 같으면 해당 인덱스를 반환하고, 그렇지 않으면 -1을 반환합니다.
예제 코드
#include <iostream>
using namespace std;
int findCoveringRange(int L[], int R[], int n) {
int minIdx = 0, maxIdx = 0;
for (int i = 1; i < n; i++) {
if (L[i] < L[minIdx])
minIdx = i;
if (R[i] > R[maxIdx])
maxIdx = i;
}
if (minIdx == maxIdx)
return minIdx;
return -1;
}
int main() {
int L[] = {2, 4, 3, 1};
int R[] = {4, 6, 7, 9};
int n = sizeof(L) / sizeof(L[0]);
cout << findCoveringRange(L, R, n);
return 0;
}출력
3
복잡도 분석
시간 복잡도: O(N) — 배열을 한 번만 순회하면 되기 때문입니다.
공간 복잡도: O(1) — 추가적인 메모리 공간이 필요하지 않습니다.