재고 기준을 넘는 구간 창고 수

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

today medium offline-fenwick 함수명: countStockThresholdQueries 제한 시간: 500ms

창고별 재고 수량과 여러 구간 조회가 주어질 때, 각 조회마다 기준 재고 이상인 창고가 구간 안에 몇 개인지 반환하는 countStockThresholdQueries 함수를 작성하세요.

문제 설명

정수 배열 stocks가 있습니다. stocks[i]는 i번 창고의 재고 수량입니다.

queries의 각 원소는 [left, right, threshold] 형태입니다. 이 조회는 left번 창고부터 right번 창고까지 중에서 재고가 threshold 이상인 창고 수를 묻습니다.

모든 조회의 답을 입력된 조회 순서대로 배열에 담아 반환하세요.

제한사항

1 <= stocks.length <= 100000
0 <= queries.length <= 100000
0 <= stocks[i] <= 1000000000
각 조회는 [left, right, threshold] 형태입니다.
0 <= left <= right < stocks.length
0 <= threshold <= 1000000000
재고가 기준값과 정확히 같은 창고도 개수에 포함합니다.
반환값은 각 조회의 답을 원래 조회 순서대로 담은 배열입니다.
조회마다 구간을 직접 모두 훑으면 큰 입력에서 시간 제한을 통과하기 어렵습니다.

예시

입력: stocks = [5, 1, 7, 3, 9], queries = [[0, 4, 5], [1, 3, 4], [2, 2, 7], [0, 1, 6]] -> 출력: [3, 1, 1, 0]
입력: stocks = [2, 2, 2], queries = [[0, 2, 2], [0, 2, 3], [1, 1, 2]] -> 출력: [3, 0, 1]
입력: stocks = [10], queries = [[0, 0, 1], [0, 0, 10], [0, 0, 11]] -> 출력: [1, 1, 0]
입력: stocks = [3, 6, 9], queries = [] -> 출력: []

힌트

기준값이 큰 조회부터 처리한다고 생각해 보세요.
현재 기준값 이상인 창고 위치만 1, 나머지는 0으로 표시하면 구간 합이 곧 답입니다.
창고를 한 번 켠 뒤에는 더 낮은 기준값의 조회에서도 계속 켜진 상태로 사용할 수 있습니다.

해설

각 조회마다 left부터 right까지 직접 확인하면 최악의 경우 O(n * q) 시간이 걸립니다. 재고 배열과 조회 수가 모두 크면 통과하기 어렵습니다.

핵심은 조회를 기준값 threshold가 큰 순서대로 처리하는 것입니다. 먼저 창고들을 재고 수량 기준 내림차순으로 정렬합니다. 조회도 threshold 내림차순으로 정렬해 둡니다.

이제 어떤 조회의 기준값이 t라면, 아직 처리하지 않은 창고 중 재고가 t 이상인 창고 위치를 Fenwick Tree에 1로 추가합니다. 이미 추가된 창고들은 앞서 더 높은 기준값을 만족했던 창고이므로, 현재 기준값도 당연히 만족합니다.

그 상태에서 Fenwick Tree의 구간 합 sum(right) - sum(left - 1)을 구하면 left..right 안에서 기준 재고 이상인 창고 수가 됩니다.

주의할 점은 조회를 정렬해서 처리하더라도 답은 원래 조회 순서대로 반환해야 한다는 것입니다. 따라서 각 조회에 원래 인덱스를 함께 저장하고, 계산한 답을 그 인덱스 위치에 넣어야 합니다.

재고가 기준값과 같은 경우도 포함해야 하므로 창고를 추가할 때 조건은 stock >= threshold입니다. 모든 재고와 조회를 정렬하는 데 O(n log n + q log q), Fenwick Tree 갱신과 조회에 O((n + q) log n)이 걸립니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과