[Swift] FloodDepth 문제 풀이 [Codility - Exercise 1. 2015 Contest]

💬 문제

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
}

 

시간 복잡도 : O(N)

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

Test results - Codility

 

 

 

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Codility/Exercise/FloodDepth.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift