새 점검 시간을 끼워 넣고 합치기
자바스크립트 코딩테스트 문제로 interval-insertion 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
이미 시작 시각 기준으로 정렬되어 있고 서로 겹치지 않는 서버 점검 구간 배열 windows와 새 점검 구간 newWindow가 주어집니다.
새 점검 구간을 기존 목록에 끼워 넣은 뒤, 겹치거나 바로 맞닿는 구간을 하나로 합쳐 시작 시각이 빠른 순서대로 반환하는 insertMaintenanceWindow 함수를 작성하세요.
예를 들어 [1, 3]과 새 구간 [2, 5]는 겹치므로 [1, 5]가 됩니다. 또한 [4, 5]와 [5, 8]처럼 끝과 시작이 같은 경우도 끊어진 시간이 없으므로 하나로 합칩니다.
제한사항
windows의 길이는0이상100,000이하입니다.windows[i]와newWindow는[start, end]형태의 정수 배열입니다.- 모든 구간은
0 <= start <= end <= 1,000,000을 만족합니다. windows는 시작 시각 오름차순으로 정렬되어 있습니다.windows안의 기존 구간들은 서로 겹치거나 맞닿아 있지 않습니다. 즉, 앞 구간의end는 다음 구간의start보다 작습니다.- 새 구간과 기존 구간이 겹치거나 맞닿으면 하나로 합쳐야 합니다.
- 반환값도 시작 시각 오름차순이며 서로 겹치거나 맞닿는 구간이 없어야 합니다.
예시
- 입력:
windows = [[1, 3], [6, 9]],newWindow = [2, 5]→ 출력:[[1, 5], [6, 9]] - 입력:
windows = [[1, 2], [4, 5], [8, 10]],newWindow = [5, 8]→ 출력:[[1, 2], [4, 10]] - 입력:
windows = [[3, 4], [7, 8]],newWindow = [0, 1]→ 출력:[[0, 1], [3, 4], [7, 8]] - 입력:
windows = [],newWindow = [4, 6]→ 출력:[[4, 6]]
힌트
- 기존 구간은 이미 정렬되어 있으므로 전체를 다시 정렬할 필요가 없습니다.
- 새 구간보다 완전히 앞에 있는 구간은 그대로 결과에 넣을 수 있습니다.
- 새 구간과 겹치거나 맞닿는 구간을 만나는 동안에는 새 구간의 시작과 끝을 계속 넓히면 됩니다.
해설
이 문제는 정렬된 구간 목록에 새 구간 하나를 추가하는 문제입니다. 모든 구간을 합친 뒤 다시 정렬해도 되지만, 기존 목록이 이미 정렬되어 있으므로 더 간단하게 한 번만 순회할 수 있습니다.
처리 구간은 세 부분으로 나눌 수 있습니다.
- 새 구간보다 완전히 앞에 있는 구간
- 새 구간과 겹치거나 맞닿아 하나로 합쳐야 하는 구간
- 새 구간보다 완전히 뒤에 있는 구간
먼저 현재 구간의 끝이 newWindow의 시작보다 작으면, 이 구간은 새 구간과 만날 수 없으므로 결과에 그대로 넣습니다.
그다음 현재 구간의 시작이 새 구간의 끝보다 작거나 같으면 두 구간은 겹치거나 맞닿아 있습니다. 이때 새 구간을 다음처럼 넓힙니다.
newStart = Math.min(newStart, start);
newEnd = Math.max(newEnd, end);
겹치는 구간을 모두 흡수한 뒤에는 넓어진 새 구간을 결과에 넣고, 아직 남은 뒤쪽 구간들을 그대로 이어 붙이면 됩니다.
이 방식은 각 기존 구간을 최대 한 번만 확인하므로 시간 복잡도는 O(n)입니다. 반환 배열을 제외하면 추가로 큰 자료구조도 필요하지 않습니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.