Lv.2arraydptwo-pointers
가장 긴 산 모양 구간
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
등산 동호회가 일정한 간격으로 측정한 등산로의 고도 기록 heights를 받았습니다. 동호회는 기록 중 연속된 구간이
다음 조건을 만족하면 "산 구간"이라고 부릅니다.
- 길이가 3 이상이고,
- 어떤 꼭대기 위치
p(구간의 처음도 끝도 아님)가 있어서, 처음부터p까지는 엄격하게 증가하고p부터 끝까지는 엄격하게 감소합니다.
가장 긴 산 구간의 길이를 반환하세요. 산 구간이 없으면 0을 반환합니다.
입출력 예
| heights | result |
|---|---|
[2, 1, 4, 7, 3, 2, 5] | 5 |
[2, 2, 2] | 0 |
[1, 3, 2, 4, 6, 5, 1] | 5 |
입출력 예 설명
예 1 — [1, 4, 7, 3, 2]가 꼭대기 7을 가진 가장 긴 산 구간입니다.
예 2 — 고도가 변하지 않으므로 산 구간이 없습니다.
예 3 — [1, 3, 2](길이 3)와 [2, 4, 6, 5, 1](길이 5) 두 산이 꼭짓점 2를 공유하며 이어져 있습니다. 더 긴 쪽은 5입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(heights: int[]) → int
제한 사항
-
heights.length -
heights[i]
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| heights | 기대 출력 |
|---|---|
[2,1,4,7,3,2,5] | 5 |
[2,2,2] | 0 |
[1,3,2,4,6,5,1] | 5 |
힌트
힌트
각 위치 i에 대해 두 값을 미리 구해 두세요.
up[i]:i에서 끝나는 엄격히 증가하는 구간이 왼쪽으로 몇 칸 이어지는가 (heights[i-1] < heights[i]이면up[i-1] + 1, 아니면0)down[i]:i에서 시작해 엄격히 감소하는 구간이 오른쪽으로 몇 칸 이어지는가 (오른쪽에서부터 같은 방식)
up[i] > 0이고 down[i] > 0인 i가 꼭대기가 될 수 있고, 그때 산의 길이는 up[i] + down[i] + 1입니다. 전체 입니다.
모든 시작점에서 산 모양이 깨질 때까지 늘려 보는 풀이는 아주 긴 산이 있을 때 이 되어 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1100 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 13 | 판정만 |
| performance | 60 | 4 | 판정만 |