Funcia
Lv.1arraybinary-search

정렬된 배열의 범위 개수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

오름차순으로 정렬된 정수 배열 nums와 질의 배열 queries가 주어집니다. 각 질의 queries[i] = [lo, hi]에 대해 lo 이상 hi 이하인 원소가 nums에 몇 개 있는지 구해, 질의 순서대로 배열에 담아 반환하세요.

nums에는 같은 값이 여러 번 들어 있을 수 있고, 모두 개수에 포함합니다.

입출력 예

numsqueriesresult
[1, 3, 3, 5, 8, 13][[3, 5], [4, 7], [0, 100], [9, 12]][3, 1, 6, 0]
[-2, 0, 0, 0, 7][[0, 0], [-5, -1]][3, 1]

입출력 예 설명

예 1 — [3, 5] 범위에는 3, 3, 5 세 개가 있습니다. [4, 7]에는 5 하나, [0, 100]에는 전부, [9, 12]에는 하나도 없습니다.

예 2 — 0이 세 번 들어 있으므로 [0, 0]의 답은 3입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(nums: int[], queries: int[][]) → int[]

제한 사항

  • 1≤1 \le nums.length ≤200,000\le 200{,}000, nums는 오름차순(같은 값 허용)으로 정렬되어 있습니다.
  • −109≤-10^9 \le nums[i] ≤109\le 10^9
  • 1≤1 \le queries.length ≤200,000\le 200{,}000
  • queries[i] = [lo, hi], −109≤lo≤hi≤109-10^9 \le lo \le hi \le 10^9

기대 복잡도

시간
O((N + Q) log N)
공간
O(1)

입출력 예

numsqueries기대 출력
[1,3,3,5,8,13][[3,5],[4,7],[0,100],[9,12]][3,1,6,0]
[-2,0,0,0,7][[0,0],[-5,-1]][3,1]

힌트

힌트

배열이 정렬돼 있으니 이분 탐색을 쓸 수 있습니다.

  • lower_bound(lo): lo 이상인 첫 원소의 위치
  • upper_bound(hi): hi 초과인 첫 원소의 위치

범위 안의 개수는 upper_bound(hi) - lower_bound(lo) 입니다. 대부분의 언어가 이 함수를 제공합니다. (C++ std::lower_bound/std::upper_bound, Python bisect_left/bisect_right, Java는 직접 구현)

직접 구현할 때는 "조건을 만족하는 첫 위치"를 찾는 형태로 쓰면 경계 실수를 줄일 수 있습니다.

복잡도 목표

질의마다 배열을 처음부터 훑는 O(NQ)O(NQ) 풀이는 효율성 테스트에서 시간 초과가 납니다. 질의당 O(log⁡N)O(\log N)이 필요합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)452 ms추정
C++ (GCC, gnu++23)452 ms도출됨
Python 3.131000 ms도출됨
Java 252196 ms도출됨
Kotlin 2.4 (JVM)1904 ms추정
C# 14 (.NET 10)1904 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness408판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.