가격 차이가 제한 이내인 연속 구간 개수

자바스크립트 코딩테스트 문제로 bounded-range-window 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium bounded-range-window 함수명: countBoundedPriceWindows 제한 시간: 300ms

가격 배열에서 최댓값과 최솟값의 차이가 제한 안인 연속 구간이 몇 개인지 구하세요.

문제 설명

정수 배열 prices와 정수 limit가 주어집니다.

연속 구간 안의 최댓값과 최솟값의 차이가 limit 이하이면 그 구간을 안정적인 가격 구간이라고 합니다.

길이가 1인 구간을 포함해 안정적인 가격 구간의 총개수를 반환하는 countBoundedPriceWindows 함수를 작성하세요.

제한사항

1 <= prices.length <= 200,000
0 <= prices[i] <= 1,000,000,000
0 <= limit <= 1,000,000,000
반환값은 JavaScript의 안전한 정수 범위 안에 들어온다고 가정합니다.
연속하지 않은 원소를 골라 만든 구간은 세지 않습니다.

예시

입력: prices = [1, 3, 2], limit = 2 -> 출력: 6
입력: prices = [8, 2, 4, 7], limit = 4 -> 출력: 6
입력: prices = [4, 4, 4], limit = 0 -> 출력: 6
입력: prices = [1, 5, 2, 3], limit = 2 -> 출력: 5

힌트

오른쪽 끝점을 하나씩 늘리면서 조건을 만족하는 가장 왼쪽 시작점을 관리해 보세요.
현재 구간의 최댓값과 최솟값을 빠르게 알 수 있도록 서로 반대 방향의 단조 deque 두 개를 사용할 수 있습니다.
오른쪽 끝점이 고정되었을 때 유효한 시작점은 몇 개인지 생각해 보세요.

해설

모든 연속 구간을 직접 확인하면 구간 수가 O(n^2)개라 입력이 클 때 통과하기 어렵습니다.

오른쪽 끝점 right를 한 칸씩 늘리는 슬라이딩 윈도우를 사용합니다. 현재 구간의 최댓값 인덱스는 값이 큰 순서로 유지하는 deque에, 최솟값 인덱스는 값이 작은 순서로 유지하는 deque에 저장합니다. 새 가격을 넣을 때 각 deque의 뒤에서 더 이상 후보가 될 수 없는 인덱스를 제거하면, 두 deque의 맨 앞에서 현재 최댓값과 최솟값을 바로 얻을 수 있습니다.

두 값의 차이가 limit를 넘는 동안 left를 오른쪽으로 옮깁니다. deque 맨 앞의 인덱스가 새로운 left보다 작아지면 함께 제거합니다. 이 과정이 끝나면 [left, right]는 조건을 만족하며, 같은 right에서 left보다 오른쪽에 있는 위치를 시작점으로 잡은 구간도 모두 조건을 만족합니다.

따라서 right에서 끝나는 안정적인 구간 수는 right - left + 1개입니다. 이 값을 모든 right에 대해 누적하면 전체 구간 수를 얻습니다.

각 인덱스는 두 deque에 각각 한 번 들어가고 최대 한 번 제거되므로 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과