[Algorithm] FloodDepth

[hwangJi-dev]

💬 문제

https://app.codility.com/programmers/trainings/1/flood_depth/

💬 Idea

• 문제 해석 후 문제 풀이 설계를 정말 꼼꼼히 해야겠다고 느꼈다…

• 많이 어려운 문제가 아니었는데, 설계를 제대로 하지 않고 무작정 코드를 짜기 시작했더니 난독증이 걸린 것 마냥 문제 안에서 헤메게 되었다.

• 물 웅덩이는 maxWall이 더 큰 수로 갱신될 때마다 새로운 웅덩이가 생기므로 큰 웅덩이가 갱신될 때 가장 작은 depth를 100000000로 초기화해주었다.

  • 이후 작은 값이 나올 때마다 minLast를 한 웅덩이 내의 가장 작은 값으로 갱신해주었다.
  • 그리고 큰 웅덩이 내에서 작은 웅덩이가 생길 때마다 maxDepth의 값과 비교하여 큰 값을 저장하도록 했다.

💬 풀이

public func solution(_ A : inout [Int]) -> Int {
    var maxWall = A[0]
    var last = A[0]
    var wall = A[0]
    var minLast = 100000000
    var maxDepth = 0
    
    for i in 1..<A.count {
        if A[i] < last {
            minLast = min(minLast, A[i])
        } else {
            // 큰 웅덩이 갱신
            if A[i] >= maxWall {
                maxDepth = max(maxWall - minLast, maxDepth)
                maxWall = A[i]
                minLast = 100000000
            } else {
                // 작은 웅덩이
                wall = A[i]
                maxDepth = max(wall - minLast, maxDepth)
            }
        }
        
        last = A[i]
    }
    
    return maxDepth
}

소요시간 : 2시간

시간 복잡도 : O(N)

평가표 : https://app.codility.com/demo/results/trainingU3M2EJ-UE5/