Funcia
Lv.2arraydptwo-pointers

가장 긴 산 모양 구간

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

등산 동호회가 일정한 간격으로 측정한 등산로의 고도 기록 heights를 받았습니다. 동호회는 기록 중 연속된 구간이 다음 조건을 만족하면 "산 구간"이라고 부릅니다.

  • 길이가 3 이상이고,
  • 어떤 꼭대기 위치 p(구간의 처음도 끝도 아님)가 있어서, 처음부터 p까지는 엄격하게 증가하고 p부터 끝까지는 엄격하게 감소합니다.

가장 긴 산 구간의 길이를 반환하세요. 산 구간이 없으면 0을 반환합니다.

입출력 예

heightsresult
[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

제한 사항

  • 1≤N=1 \le N = heights.length ≤200,000\le 200{,}000
  • 0≤0 \le heights[i] ≤109\le 10^9

기대 복잡도

시간
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입니다. 전체 O(N)O(N)입니다.

모든 시작점에서 산 모양이 깨질 때까지 늘려 보는 풀이는 아주 긴 산이 있을 때 O(N2)O(N^2)이 되어 시간 초과가 납니다.

언어별 시간 제한

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

테스트 그룹

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

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