Funcia
Lv.2arrayprefix-sumtwo-pointers

고이는 빗물

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

정수 배열 A가 주어집니다. A[i]는 i번째 자리에 세워진 건물의 높이입니다. 각 자리의 너비는 1입니다.

비가 충분히 내린 뒤 건물 사이에 고이는 물의 총량을 반환하세요. 배열의 양쪽 바깥은 뚫려 있어 물이 흘러 나갑니다.

입출력 예

Aresult
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]6
[4, 2, 0, 3, 2, 5]9
[3, 2, 1]0

입출력 예 설명

예 2 — 그림으로 보면 이렇습니다. #은 건물, ~는 고인 물입니다.

 5              #
 4  #  ~  ~  ~  #
 3  #  ~  ~  #  #
 2  #  #  ~  #  #  #
 1  #  #  ~  #  #  #
 0  #  #  #  #  #  #
    4  2  0  3  2  5

칸별 물의 양은 0, 2, 4, 1, 2, 0으로 합이 9입니다.

예 3 — 계속 낮아지기만 하므로 물이 고이지 않습니다.

효율성

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

Function signature

solution(A: int[]) → long

Constraints

  • 1≤N≤200,0001 \le N \le 200{,}000
  • 0≤A[i]≤1090 \le A[i] \le 10^9
  • 답은 64비트 정수 범위입니다.

Expected complexity

Time
O(N)
Space
O(N)

Examples

AExpected
[0,1,0,2,1,0,1,3,2,1,2,1]6
[4,2,0,3,2,5]9
[3,2,1]0

Hint

Hint

칸 하나만 떼어놓고 생각하세요. i번 칸 위에 고이는 물의 높이는 양쪽 벽 중 낮은 쪽까지입니다.

물[i]=min⁡(왼쪽 최댓값, 오른쪽 최댓값)−A[i]\text{물}[i] = \min(\text{왼쪽 최댓값},\ \text{오른쪽 최댓값}) - A[i]

그러니 각 위치의 왼쪽 최댓값 배열과 오른쪽 최댓값 배열을 각각 한 번씩 훑어 만들어두면 됩니다. 두 배열 모두 자기 자신을 포함해서 만들면 위 식이 음수가 되지 않아 따로 처리할 게 없습니다.

역방향 루프는 시작 N-2, 조건 >= 0, 증감 i-- 세 요소를 함께 확인하세요.

복잡도 목표

각 칸마다 양쪽을 다시 훑는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251400 msestimated
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1000 msderived

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.