💬 문제
[a, b] 형식으로 나타낸 구간 배열 intervals
겹치는 구간을 하나로 합친 배열 반환
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]✍️ 나의 풀이
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
intervals.sort((a, b) => {
return a[0] - b[0];
});
let res = [];
let start = 0;
let max = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= max) {
max = Math.max(max, intervals[i][1]);
continue ;
}
res.push([intervals[start][0], max]);
start = i;
max = intervals[i][1];
}
res.push([intervals[start][0], max]);
return res;
};한번만 반복하기 위해 가장 먼저 정렬을 하고 시작
두번째 인덱스부터 시작하여 구간 비교
현재 구간의 시작점이 이전까지 합쳐진 구간들 중 가장 큰 수의 종료점보다 작다면
이번에도 합쳐질 수 있으므로 max 종료점 비교 후에 넘어감
합쳐질 수 없는 구간을 만났다면 이전까지의 구간들을 합쳐서
시작점(정렬을 했으므로 시작 인덱스의 첫번째 값이면 됨)과 max 종료점 배열에 넣기
마지막 인덱스는 확인만 하고 넣지 못했으므로 for문 끝나고 한번 더 넣어주기
(for문 조건을 바꾸지 않은 이유는 참조에러 때문에)
📌 결과
Accepted
Runtime 94ms (Beats 62.95%)
Memory 59.86MB (Beats 31.80%)
📚 러닝 포인트
바로 이전 문제랑 비슷하게 구현해 보았다. 테스트케이스 예제는 정렬이 되어 있길래 그걸 전제로 짰었는데 아니어서 정렬 넣었다. 이후에도 자잘하게 챙기지 못했던 테케가 몇 번 나와서 수정을 여러번 했는데, 특히 for문 내에 if (intervals[i][0] <= max) 이 부분이 원래는 if (intervals[i][0] <= intervals[i - 1][1]) 이거였다. 정렬을 했으니까 단순히 앞 인덱스 종료점 안에 현재 인덱스 시작점이 포함되면 되는거 아닌가 생각했었는데 테케를 보니까 어떤 건 앞 구간 안에 전부 들어가고, 어떤 건 앞구간이랑 합쳐서 확장될 수 있는 구간이 있기도 했다. 그래서 max 값이 필요하다는 걸 깨닫고 변수 추가 후에 조건이랑 push할 값도 전부 변경했다.
