빗물[백준 14719 파이썬]

문제 설명

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력
2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

전체 코드

h, w = list(map(int, input().split()))
arr = list(map(int, input().split()))

answer = 0

# 투포인터 풀이. 왼쪽 오른쪽에서 각각 출발하여
# 가운데(반드시 가운데는 아니고 양 가장자리일 수도 있다.)의 가장 긴 높이에 있는 곳에 도착하는 게 목적.
left = 0
right = len(arr) - 1

left_max = arr[left]
right_max = arr[right]

while left < right:  # 종료 조건은 결국 두 포인터가 가장 긴 높이에 있는 곳에 모두 도착할 때 이다.
    # 왼쪽에서 가장 큰 값 찾기
    left_max = max(left_max, arr[left])

    # 오른쪽에서 가장 큰 값 찾기
    right_max = max(right_max, arr[right])

    # 두 최댓값 중 더 작은 값의 방향을 택한다.
    if left_max < right_max:  # 왼쪽 최댓값이 더 적을 경우
        answer += (left_max - arr[left])  # 왼쪽 최댓값 - arr[left] 하면 차이가 나오므로 누적.
        left += 1  # -> 전진

    else:  # 오른쪽 최댓값이 더 적을 경우
        answer += (right_max - arr[right])  # 오른쪽 최댓값 - arr[right]하면 차이가 나오므로 누적.
        right -= 1  # <- 전진

print(answer)

느낀 점

leetcode에서 못 풀었던 것 백준에서도 못 풀어서 좀 아쉽다. 여러 번 풀어서 체득해야겠다.