최고 신호가 가장 먼저 도달한 방
자바스크립트 코딩테스트 문제로 difference-array 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
n개의 방이 일렬로 있고, 각 신호 증폭 작업은 특정 구간의 방들에 같은 세기만큼 신호를 더하거나 뺍니다. 모든 작업이 끝난 뒤 신호 세기가 가장 큰 방 번호와 그 세기를 [방 번호, 신호 세기] 형태로 반환하세요. 가장 큰 세기를 가진 방이 여러 개라면 가장 번호가 작은 방을 반환합니다.
제한사항
1 <= n <= 100,0001 <= boosts.length <= 100,000- 각 작업은
[start, end, delta]형태입니다. 1 <= start <= end <= n-100,000 <= delta <= 100,000- 모든 방의 초기 신호 세기는
0입니다. - 반환값은
[earliestRoom, maxSignal]형태의 길이 2 배열입니다.
예시
- 입력:
n = 8,boosts = [[1, 3, 2], [2, 5, 1], [6, 8, 3]]→ 출력:[2, 3] - 입력:
n = 5,boosts = [[1, 5, 4], [2, 4, -2], [3, 3, 5]]→ 출력:[1, 4] - 입력:
n = 4,boosts = [[1, 4, -1], [2, 3, 2]]→ 출력:[2, 1]
힌트
- 작업 하나마다 구간 전체를 직접 더하면 최악의 경우 너무 느립니다.
- 어떤 구간이 시작되는 지점과 끝난 다음 지점만 기록해 두면, 마지막에 한 번의 누적 합으로 각 방의 신호를 복원할 수 있습니다.
- 최대 신호를 갱신할 때는 동률이면 더 작은 방 번호를 유지해야 합니다.
해설
이 문제를 단순하게 풀면 각 작업 [start, end, delta]마다 start부터 end까지 모두 방문해서 delta를 더하게 됩니다. 하지만 방 개수와 작업 개수가 둘 다 최대 100,000이므로, 최악의 경우 O(n * boosts.length)가 되어 너무 느립니다.
여기서 핵심은 차분 배열(difference array) 입니다.
작업 [start, end, delta]가 있으면:
diff[start] += deltadiff[end + 1] -= delta(범위 안에 있을 때만)
이렇게만 기록해 두면, 나중에 1번 방부터 차례대로 누적 합을 구할 때 실제 각 방의 신호 세기를 복원할 수 있습니다.
예를 들어 [2, 5, 3]이라는 작업은:
- 2번 방부터 신호가
+3시작되고 - 6번 방부터 그 효과가 끝난다고 표시하는 것과 같습니다.
이후 1번부터 n번까지 누적 합을 구하면서:
- 현재 방의 실제 신호 세기를 계산하고
- 지금까지 본 최대값보다 크면 정답을 갱신하고
- 같다면 더 이른 방 번호를 유지합니다.
즉, 전체 흐름은 다음과 같습니다.
- 길이
n + 2정도의 차분 배열을 0으로 만든다. - 각 작업에 대해 시작점과 끝 직후 지점만 갱신한다.
- 1번 방부터 누적 합을 구한다.
- 최대 신호와 가장 빠른 방 번호를 함께 관리한다.
이 방법의 시간 복잡도는 O(n + boosts.length)이고, 공간 복잡도는 O(n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.