프로그래밍을 하다 보면 두 개의 범위 집합을 비교해야 하는 경우가 자주 있습니다. 하나는 임의의 길이를 가진 단일 범위(R1)이고, 다른 하나는 여러 개의 구간으로 이루어진 범위 집합(R2)입니다. 이때 R2에 속한 구간들 중 R1 내부에 완전히 또는 부분적으로 포함되는 부분의 길이를 모두 합산하는 것이 이번 글의 목표입니다.
문제 정의
먼저 다음과 같은 데이터가 주어졌다고 가정해 보겠습니다.
const R1 = [20,40]; const R2 = [[14,22],[24,27],[31,35],[38,56]];
R2의 각 구간이 기준 범위 R1([20, 40])과 어떻게 겹치는지 살펴보면 다음과 같습니다.
- [14, 22] → [20, 22] 구간만 겹침 → 길이 2
- [24, 27] → R1에 완전히 포함 → 길이 3
- [31, 35] → R1에 완전히 포함 → 길이 4
- [38, 56] → [38, 40] 구간만 겹침 → 길이 2
결과
= 2+3+4+2 = 11
두 번째 예시도 확인해 보겠습니다.
R1 = [120,356]; R2 = [[234,567]];
구간 [234, 567]은 시작점(234)은 R1 내부에 있지만 끝점(567)은 R1의 끝(356)을 벗어납니다. 따라서 실제로 겹치는 부분은 [234, 356]이며, 그 길이는 122입니다.
결과
122
해결 코드
이 문제는 배열의 reduce() 메서드를 활용하면 간결하게 해결할 수 있습니다. 핵심 아이디어는 각 구간마다 기준 범위와의 교집합(겹치는 구간)의 길이를 계산한 뒤 모두 누적하는 것입니다.
const R1 = [20,40];
const R2 = [[14,22],[24,27],[31,35],[38,56]];
const R3 = [120,356];
const R4 = [[234,567]];
function sumRanges(range, values) {
const [start, end] = range;
const res = values.reduce((acc, val) => {
const [left, right] = val;
const ex1 = Math.min(right, end);
const ex2 = Math.max(left, start);
const diff = ex1 - ex2;
return acc + Math.max(0, diff);
}, 0);
return res;
};
console.log(sumRanges(R1, R2));
console.log(sumRanges(R3, R4));
출력 결과
코드를 실행하면 콘솔에 다음과 같이 출력됩니다.
11 122
코드 동작 원리
알고리즘의 핵심 로직을 단계별로 살펴보겠습니다.
- 교집합의 오른쪽 경계 계산:
Math.min(right, end)를 사용해 현재 구간의 끝점과 기준 범위의 끝점 중 더 작은 값을 선택합니다. - 교집합의 왼쪽 경계 계산:
Math.max(left, start)를 사용해 현재 구간의 시작점과 기준 범위의 시작점 중 더 큰 값을 선택합니다. - 겹침 길이 계산: 두 경계값의 차이(
ex1 - ex2)가 곧 두 범위가 겹치는 구간의 길이입니다. - 음수 값 처리: 구간이 기준 범위와 전혀 겹치지 않으면 위 차이가 음수가 됩니다. 이때
Math.max(0, diff)를 적용해 음수인 경우 0으로 만들어 잘못된 누적을 방지합니다.
이 방식은 각 구간을 한 번씩만 순회하면 되므로 시간 복잡도가 O(n)으로 매우 효율적입니다. 또한 R2의 구간들이 정렬되어 있지 않거나 서로 겹쳐 있더라도 정확한 결과를 얻을 수 있다는 장점이 있습니다.