[Python] Codility FloodDepth

이 문제는 "Trapping Rain Water" 문제를 변형하여 최대 물 깊이를 구하는 문제

 

빗물이 가장 깊게 고인 곳의 깊이는?

 

먼저 빗물이 고이기 위해서는 왼쪽 오른쪽에 현재 위치보다 높은 땅이 있어야한다.

따라서 각 인덱스에서 왼쪽 기둥 오른쪽 기둥을 구해야한다.

left_max = [0 for _ in range(n)]
right_max = [0 for _ in range(n)]

left_max[0] = A[0]

for i in range(1,n):
    left_max[i] = max(left_max[i-1], A[i])

right_max[n-1] = A[n-1]
for i in range(n-2,-1,-1):
    right_max[i] = max(right_max[i+1], A[i])

 

 

그 후에 빗물의 깊이를 구해야한다. 이를 water_level로 하며 왼쪽 기둥, 오른쪽 기둥 중 낮은 위치를 구한 후 낮은 위치에 있는 수심과의 차이를 구한다. 수심이 가장 깊은 곳을 구해야하므로 다음과 같이 구현할 수 있다.

max_depth = 0

for i in range(1, n-1):
    water_level = min(left_max[i-1], right_max[i+1])
    if water_level > A[i]:
        max_depth = max(max_depth, water_level - A[i])

 

 

CODE

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # Implement your solution here
    n = len(A)

    if n < 3:
        return 0
    
    left_max = [0 for _ in range(n)]
    right_max = [0 for _ in range(n)]

    left_max[0] = A[0]

    for i in range(1,n):
        left_max[i] = max(left_max[i-1], A[i])
    
    right_max[n-1] = A[n-1]
    for i in range(n-2,-1,-1):
        right_max[i] = max(right_max[i+1], A[i])
    
    max_depth = 0

    for i in range(1, n-1):
        water_level = min(left_max[i-1], right_max[i+1])
        if water_level > A[i]:
            max_depth = max(max_depth, water_level - A[i])
    return max_depth