백준 - 빗물(Swift)

백준 - 빗물(Swift)

 

 

 문제 설명

 

https://www.acmicpc.net/problem/14719

14719번: 빗물

 

 나의 풀이

 

문제를 보자마자 언제 빗물이 차는지 규칙을 찾으려고 했다. 

그래서 찾은 규칙은 처음부터 탐색할 때 들어오는 블록을 기준선으로 놓고 기준선보다 크거나 같은 블럭이 나올때마다 그 사이의 값들을 기준선으로 빗물을 채워준다는 규칙을 찾았다. 주의할 점은 처음 기준선을 정할 때만 flag를 줌으로써 계속해서 기준선이 리셋되는 것을 방지하는 것이다. x가 1보다 크다는 조건을 넣었기 때문에 끝이 비어있는 경우를 방지할 수 있다. 

 

사실 별로 좋지않은 풀이인 것 같다고 생각해서 다른 분들의 풀이를 찾아보았다.

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
let H = input[0], W = input[1]
let arr = readLine()!.components(separatedBy:" ").map{Int($0)!}

var visited = [Bool](repeating: false, count: W) // 빗물을 채웠는지
var flag = false 
var baseLine = H+1
var baseIdx = 0
var result = 0

for (i, x) in arr.enumerated() {
    if x >= 1 && !flag { 
        baseLine = x
        baseIdx = i
        flag = true
    } else if baseLine <= x {
        for j in baseIdx+1..<i {
            if !visited[j] {
                result += baseLine - arr[j]
                visited[j] = true
            }
        }
        baseLine = x
        baseIdx = i
    }
}
flag = false

for i in stride(from: W-1, to: -1, by: -1) {
    if arr[i] >= 1 && !flag {
        baseLine = arr[i]
        baseIdx = i
        flag = true
    } else if baseLine <= arr[i] {
        for j in stride(from: baseIdx-1, to: i, by: -1) {
            if !visited[j] {
                result += baseLine - arr[j]
                visited[j] = true
            }
        }
        baseLine = arr[i]
        baseIdx = i
    }
}

print(result)

 

 

 

 다른 사람의 풀이

 

특정 위치를 기준으로 왼쪽의 최대값과 오른쪽의 최대값중에 더 작은 값만큼 빗물을 채워주는 방식이다.

이를 위해서 각 인덱스에서의 최대값을 구해줬다.

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
let H = input[0], W = input[1]
let arr = readLine()!.components(separatedBy:" ").map{Int($0)!}

var leftMax = [Int](repeating: 0, count: arr.count)
var rightMax = [Int](repeating: 0, count: arr.count)
var result = 0
leftMax[0] = arr[0]
rightMax[arr.count-1] = arr.last!

for i in 1..<arr.count {
    leftMax[i] = max(leftMax[i-1], arr[i])
}

for i in (0..<arr.count-1).reversed() {
    rightMax[i] = max(rightMax[i+1], arr[i])
}

for i in 1..<arr.count-1 {
    result += min(leftMax[i], rightMax[i]) - arr[i]
}

print(result)