백준 14719 빗물

출처: www.acmicpc.net/problem/14719

분류: 구현, 시뮬레이션

---

접근방식

고이는 빗물의 양을 구하는 문제였습니다. 고이는 빗물은 자신의 양쪽에 자신보다 더 큰 빗물이 있어야 합니다.

저는 처음에 스택으로 접근을 했는데요.

스택에 인덱스와 높이를 넣어주는데, 스택의 탑보다 더 작은 블록을 만나면 추가하고 같으면 새로운 블록으로 갈아치워줍니다.

더 큰 블록을 만나면 탑의 왼쪽과 새로 만난 블록 중 더 작은 높이를 비교하고 스택의 탑에 있는 인덱스와 지금 블록을 비교해서 둘 중 더 작은 높이와 탑의 높이를 빼서, 빗물을 채워주는 방식을 사용했었습니다.

가로 방향으로 칸칸히 채워나가는 방식을 생각했었습니다. 하지만 이렇게 하면, 왼쪽이나 오른쪽 끝이 비어있을 때 문제가 됩니다. 이를 별도로 어떻게 처리해준다면 될 것도 같은데.. 복잡하더라구요 ㅠㅠ

그래서 다른 분들의 풀이를 참고했습니다. 가로로 채워나가는 것이 아니라, 

자신의 왼쪽 중 가장 큰 블록과 오른쪽 중 가장 큰 블록을 비교해서 둘중 더 작은 값으로 세로로 채워나가는 방식으로 해결했습니다.

이를 위해 먼저 왼쪽부터 현재 인덱스에서 왼쪽의 가장 큰 값을 가진 배열과 오른쪽부터 가장 큰 값을 담은 배열 두 개를 만들어주고

왼쪽과 오른쪽 중 더 작은 값으로 세로로 채워주는 방식으로 해결할 수 있었습니다.

 

해결방법

let hw = readLine()!.split(separator: " ").map { Int(String($0))! }
let blocks = readLine()!.split(separator: " ").map { Int(String($0))! }

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

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

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

var dropValue = 0
for i in 1..<blocks.count-1 {
    dropValue += min(leftMax[i], rightMax[i]) - blocks[i]
}

print(dropValue)

 

배운점

풀고나니 어려운 문제는 아니었지만... 실제 시험에서 처음 접근의 반례를 찾지 못하고 잘못 접근했다면 바로 틀렸을 것이다. 아찔하다... ㅠㅠ

내공을 더 쌓아야 한다!!! 🔥