[백준] 14719번: 빗물

문제

백준 - 14719번: 빗물

분석

블록 높이가 차례로 주어졌을 때, 고이는 빗물의 총량을 구하는 문제이다.

스택

높이에 관한 문제들을 풀었던 경험상, 스택을 이용한 적이 많았어서 이번에도 스택을 사용해야겠다는 생각을 먼저했다.

스택을 이용한 풀이에서는 빗물이 현재 위치에서 어떤 높이까지 찰 것인지는 알 수가 없다. 후에 나오는 블록에 따라 달라질 것이기 때문이다.
그래서 일단 낮아지다가 높아졌을 때(같아도) 양 끝 중 더 낮은 블록에다가 중간에 있던 블록 높이를 뺀 것이 높이가 되고, 너비는 그 둘 위치의 차에서 1을 뺀 값이 되어, 그 둘을 곱한 것이 물이 찬 양이 된다. 가로로 물이 차는 것을 생각하면 쉽다.

스택에는 높이[0]와, 위치[1]를 넣는다.
스택의 탑의 높이 값이 현재 비교하는 높이보다 작거나 같다면 pop한다.
스택이 남아있지 않으면 왼쪽에서 막아줄 블록이 없으므로 물이 고이지 않는다.
남아있다면 스택 탑의 높이 값과, 현재 비교하는 높이 둘 중 작은 것에 아까 pop한 높이를 빼면 고일 물의 높이가 된다. 그리고 현재 위치에서 스택 탑의 위치 값을 빼고 1을 더 빼주면 고일 물의 너비가 되어 그 둘을 곱한 값을 누적하면 된다.

LR Technique

문제를 다 풀고 더 빠르게 푼 사람들의 코드를 보다가 훨씬 쉽게 접근해서 나도 다시 풀어봤다.
L배열에는 왼쪽부터 순회했을 때 가장 높은 값을 넣어준다.
R배열에는 오른쪽부터 순회했을 때 가장 높은 값을 넣어준다.
그리고 각자의 위치에서 고일 빗물의 양을 더해주면 된다.
각 위치에서 왼쪽에서 가장 높은 것과, 오른쪽에서 가장 높은 것을 알기 때문에 그 중 낮은 것에서 현재의 블록 높이를 빼주면 고일 빗물의 양을 알 수 있다.

코드

해결언어 : Python
스택 풀이

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
heights = list(map(int, input().split()))
stack = []
water = 0
for i in range(w):
    while stack and stack[-1][0] <= heights[i]:
        h, _ = stack.pop()
        if stack:
            water += (min(stack[-1][0], heights[i])-h)*(i-stack[-1][1]-1)
    stack.append((heights[i], i))
print(water)

LR Technique 풀이

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
heights = list(map(int, input().split()))
L = [0]*w
R = [0]*w
L[0] = heights[0]
for i in range(1, w):
    L[i] = max(L[i-1], heights[i])
R[-1] = heights[-1]
for i in range(w-2, -1, -1):
    R[i] = max(R[i+1], heights[i])

water = 0
for i in range(1, w-1):
    water += min(L[i], R[i]) - heights[i]
print(water)

끝으로..

LR Technique은 알고 있었지만 바로 적용할 생각을 못했다.
관련 문제를 더 풀어봐야겠다.