Codility FloodDepth

바위들 중, 가장 깊은 웅덩이의 깊이를 알아내는 문제입니다.

이 문제의 알고리즘은 바위의 가장 높은 곳을 가르키는 peak와 새로운 peak가 나오기 전까지의 가장 낮은 바위의 row값을 알아내어 그 차를 구해 가장 큰값을 구하는 알고리즘 입니다.

1. 웅덩이가 발생하는 곳을 알아내는 것(내리막이 발생하는 지점), 만약 웅덩이가 발생한다면 현재까지의 웅덩이 중 가장 낮은지 row와 비교한다.

2. 오르막이 발생한다면, 웅덩이가 발생하는 곳 이전에 있던 바위들 중의 가장 높은 바위의 길이(peak)와 오르막이 발생한 지점의 바위높이 중 낮은 바위의 높이에서 지금까지 가장낮은 바위높이인 row값을 빼줍니다.

depth = min(peak, rock[index+1]) - row

3. 이때, 새로운 peak가 갱신된다면 row를 초기화해줍니다.(peak가 생김으로 새로운 웅덩이가 생길 가능성이 있음.)

 

def solution(A):
    answer = 0

    A.insert(0, 0)
    A.append(0)
    peak = 0
    min_v = 1000000000
    for index in range(len(A)-1):
        if A[index] < A[index+1]:
            answer = max(answer, min(A[index + 1], peak) - min_v)
            if peak < A[index+1]:
                peak = A[index+1]
                min_v = 1000000000
        else:
            min_v = min(min_v, A[index+1])
    return answer

간단한 문제인데도 반례를 찾느라 시간이 오래걸렸습니다. 반성이 되네요,ㅠ