문제 상황
2차원 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
입력 배열의 각 하위 배열은 정확히 두 개의 숫자로 구성되어 있으며, 하나의 시간 구간(간격)을 나타냅니다.
함수는 다른 구간에 완전히 포함되는 모든 구간을 제거한 뒤, 배열에 남아 있는 구간의 개수를 반환해야 합니다. 여기서 구간 [a, b)가 구간 [c, d)에 포함된다는 것은 c <= a 이고 b <= d일 때, 그리고 그 경우에만 성립합니다.
예를 들어 함수의 입력이 다음과 같다면,
const arr = [ [2, 5], [5, 7], [3, 9] ];
출력은 다음과 같아야 합니다.
const output = 2;
출력 설명
구간 [5, 7]은 시작점과 끝점이 모두 구간 [3, 9] 안에 들어가므로 [3, 9]에 포함됩니다. 따라서 [5, 7]은 제거되고, 최종적으로 남는 구간은 [2, 5]와 [3, 9] 두 개입니다.
접근 방법
이 문제는 정렬과 한 번의 순회만으로 효율적으로 해결할 수 있습니다.
먼저 구간을 시작점 기준으로 오름차순 정렬합니다. 만약 시작점이 같다면 끝점이 더 큰(즉, 더 긴) 구간을 앞쪽에 배치합니다. 이렇게 하면 현재 검사 중인 구간보다 앞에 있는 구간만이 현재 구간을 포함할 수 있습니다.
정렬 후에는 배열을 순회하면서 각 구간이 직전에 저장해 둔 구간(last)에 포함되는지 확인합니다. 포함된다면 카운트를 하나 줄이고, 포함되지 않는다면 해당 구간을 새로운 기준 구간으로 갱신합니다.
구현 예제
이를 코드로 구현하면 다음과 같습니다.
const arr = [
[2, 5],
[5, 7],
[3, 9]
];
const removeCovered = (arr = []) => {
// 시작점 오름차순, 같으면 더 긴 구간이 먼저 오도록 정렬
arr.sort(([a, b], [c, d]) => (a === c ? d - b : a - c));
let last = arr[0];
let count = arr.length;
for(let i = 1; i < arr.length; i++){
const [a, b] = last;
const [c, d] = arr[i];
if(c >= a && d <= b){
// 현재 구간이 last 구간에 포함되는 경우
count -= 1;
}else{
// 포함되지 않으므로 기준 구간을 갱신
last = arr[i];
};
};
return count;
};
console.log(removeCovered(arr));실행 결과
콘솔에는 다음과 같이 출력됩니다.
2
복잡도 분석
정렬에 O(n log n)의 시간이 걸리고, 이후 순회는 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 추가로 사용하는 공간은 정렬에 필요한 공간 외에는 상수 수준으로, 공간 복잡도는 O(1)(정렬 자체의 보조 공간 제외)입니다.