Lv.3segment-treesparse-table
구간 최솟값 질의
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
어느 산길의 지점별 고도가 정수 배열 values로 주어집니다. 등산객들이 "l번 지점부터 r번 지점까지 걸으면 가장 낮은 곳의 고도는 얼마인가요?"라고 묻습니다.
queries[j] = [l, r]마다 values[l], values[l+1], …, values[r] 중 최솟값을 구해 질문 순서대로 배열에 담아 반환하세요.
values는 바뀌지 않습니다.
입출력 예
| values | queries | result |
|---|---|---|
[5, 2, 8, 6, 3, 7] | [[0, 5], [2, 3], [3, 5], [4, 4]] | [2, 6, 3, 3] |
[-1, -1, 0] | [[1, 2], [0, 0]] | [-1, -1] |
입출력 예 설명
예 1 — 전체 구간의 최솟값은 2, [2, 3] 구간 {8, 6}의 최솟값은 6, [3, 5] 구간 {6, 3, 7}의 최솟값은 3입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(values: int[], queries: int[][]) → int[]
제한 사항
-
values.length,values[i] -
queries.length -
lr
기대 복잡도
- 시간
- O(N log N + Q)
- 공간
- O(N log N)
입출력 예
| values | queries | 기대 출력 |
|---|---|---|
[5,2,8,6,3,7] | [[0,5],[2,3],[3,5],[4,4]] | [2,6,3,3] |
[-1,-1,0] | [[1,2],[0,0]] | [-1,-1] |
힌트
힌트
배열이 바뀌지 않으므로 미리 표를 만들어 두고 질문마다 빠르게 답할 수 있습니다.
희소 테이블(sparse table): t[k][i] = values[i .. i + 2^k - 1]의 최솟값으로 정의하면
로 에 만들 수 있습니다. 질문 [l, r]은 길이 에 대해 인 가장 큰 를 골라
로 답합니다. 두 구간이 겹쳐도 최솟값에는 영향이 없기 때문에 입니다. (세그먼트 트리로 에 답해도 됩니다.)
복잡도 목표
질문마다 구간을 직접 훑는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 222 ms | 추정 |
| C++ (GCC, gnu++23) | 222 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 2248 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1444 ms | 추정 |
| C# 14 (.NET 10) | 1444 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |