겹치는 구간 한 번에 합치기
자바스크립트 코딩테스트 문제로 intervals 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
숫자 구간 목록 ranges가 주어질 때, 서로 겹치거나 끝점에서 맞닿아 있는 구간들을 합친 뒤 새로운 구간 목록을 반환하는 solution 함수를 작성하세요.
각 구간은 [start, end] 형태이며 start <= end입니다.
반환 결과는 시작점 오름차순으로 정렬되어 있어야 합니다.
예를 들어 [[1, 3], [2, 6], [8, 10], [15, 18]]이라면 앞의 두 구간이 겹치므로 [[1, 6], [8, 10], [15, 18]]을 반환해야 합니다.
제한사항
1 <= ranges.length <= 100000- 각 구간은
[start, end]형태의 길이 2 배열입니다. -1000000000 <= start <= end <= 1000000000- 입력 구간의 순서는 정렬되어 있지 않을 수 있습니다.
[a, b]와[b, c]처럼 끝점과 시작점이 같은 경우도 하나의 구간으로 합칩니다.- 반환 결과의 각 구간은 서로 겹치지 않아야 합니다.
예시
- 입력:
[[1, 3], [2, 6], [8, 10], [15, 18]]→ 출력:[[1, 6], [8, 10], [15, 18]] - 입력:
[[5, 7], [1, 2], [2, 4]]→ 출력:[[1, 4], [5, 7]] - 입력:
[[1, 4], [4, 5]]→ 출력:[[1, 5]]
힌트
- 구간이 뒤섞여 들어오면 바로 병합하기 어렵습니다.
- 먼저 시작점 기준으로 정렬하면, 현재 구간이 마지막 병합 구간과 겹치는지만 보면 됩니다.
- 마지막 병합 구간의 끝점보다 현재 시작점이 크면 새로운 구간을 시작해야 합니다.
해설
이 문제의 핵심은 정렬 후 앞에서부터 병합한다는 점입니다.
입력 순서 그대로 처리하면 뒤에 더 이른 시작점을 가진 구간이 나올 수 있어서 안정적으로 합치기 어렵습니다. 그래서 먼저 구간을 시작점 기준으로 정렬합니다.
예를 들어 [[5, 7], [1, 2], [2, 4]]는 정렬하면 [[1, 2], [2, 4], [5, 7]]이 됩니다.
그다음 결과 배열을 하나 만들고, 현재 구간을 보면서 마지막 병합 구간과 비교합니다.
- 결과 배열이 비어 있으면 현재 구간을 그대로 넣습니다.
- 마지막 병합 구간의 끝점이 현재 구간의 시작점 이상이면 두 구간은 겹치거나 맞닿아 있으므로 합칠 수 있습니다.
- 이때 끝점을
Math.max(기존 끝점, 현재 끝점)으로 늘립니다.
- 이때 끝점을
- 그렇지 않으면 완전히 떨어진 구간이므로 새 구간을 결과에 추가합니다.
왜 이 방식이 맞을까요? 정렬을 해 두었기 때문에, 현재 구간보다 뒤에 있는 구간들은 시작점이 더 작아질 일이 없습니다. 따라서 지금 시점에서 비교해야 할 대상은 결과의 마지막 구간 하나만 있으면 충분합니다.
예를 들어 정렬된 구간이 다음과 같다고 합시다.
[1, 3][2, 6][8, 10]
첫 번째 구간 [1, 3]을 넣고,
두 번째 구간 [2, 6]은 시작점 2가 마지막 끝점 3 이하이므로 병합해서 [1, 6]이 됩니다.
세 번째 구간 [8, 10]은 시작점 8이 마지막 끝점 6보다 크므로 새 구간으로 분리됩니다.
이 방법의 시간 복잡도는 정렬 때문에 O(n log n)이고, 정렬 후 병합 과정은 O(n)입니다.
알고리즘별 코테 관점에서는 정렬 후 한 번 스캔하면서 상태를 압축하는 전형적인 interval 문제 감각을 익히기에 좋습니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.