i의 위치에 고이는 빗물의 높이를 구하는 방법은. i를 중심으로 각각 왼쪽, 오른쪽에서 가장 높은 블록의 높이를 구한 다음, 이 두 개의 높이 중 작은 쪽과 i위치의 높이를 빼면 고인 빗물의 높이를 구할 수 있습니다. A를 블록의 정보가 저장되어 있는 배열로 가정할 때, A[i]에 채울 수 있는 빗물의 최대 높이는 min(A[left], A[right]) - A[i] 입니다.
범위는 left의 경우 0부터 i-1 까지, right는 i+1부터 마지막 블록 까지 범위를 잡고 계산하면 됩니다.
하지만 위와 같이 A[i]의 빗물 높이가 0이 되는 경우도 있습니다, 이 경우 min(A[left] - A[right]) - A[i]가 0이하가 되는 겨우 입니다. 즉, 음수가 되는 경우도 있으니, 식을 max(0, min(A[left] - A[right]) - A[i])로 바꿉니다. 이래야 음수가 되는 경우 max 함수로 인해 0으로 판정이 됩니다.
Function Solution(A: Array of Integer, W: Integer, H: Integer): Integer
// A -> 블록의 정보가 담겨 있는 배열
// W: 너비, H: 높이
x <- 0
for i <- 1 to W-2 do
// 0번째와 맨 마지막은 빗물 높이가 0이므로 구할 필요가 없다.
l <- -1
r <- -1
// left
for j <- 0 to i-1 do
l <- Max(l, A[j])
endFor
// right
for j <- i+1 to W-1 do
r <- Max(r, A[j])
endFor
// i위치의 빗물 높이 구하기
x <- (x + Max(0, Min(l, r) - A[i])
endFor
return x
EndFunction
하지만 위의 방식으로는 어디까지나 너비와 높이가 좁은 경우에만 가능하며 광범위한 범위일 경우, 상당한 시간이 걸립니다. 리트코드에서는 백준 기준 난이도가 골드5 임에도 불구하고 이러한 이유로 Hard로 책정되어 있습니다. 백준에서 했던 방식으로 제출하면 시간 초과가 발생합니다.
left와 right를 구하는 과정에서 for문을 쓰지 않고, 맨 처음에 왼쪽, 또는 오른쪽 부터 특정 i까지 가장 높은 블록을 저장(누적합)을 미리 저장을 해 두면 시간 안에 풀 수 있으나, 여전히 시간이 많이 걸립니다. left, right를 미리 저장해 둔 경우 시간 안에 풀 수 있지만 아래의 방법을 이용해 더 빨리 풀 수 있다.
발상의 전환이 조금 필요합니다. 0부터 차례대로 스택을 쌓다가, i번째 블록이 스택의 맨 앞에 있는 블록의 높이보다 더 클 경우, i위치의 블록의 높이가 스택 앞에 있는 블록보다 작거나 같을 때 까지 스택의 값들을 꺼내며 값을 계산합니다. 위의 예시를 통해 방법을 알아봅시다.
인덱스 2 까지는 블록의 높이가 감소하고 있기 때문에 아무런 작업 없이 스택에 계속 추가합니다. 특정 작업이 수행되는 시점은 i 위치의 블록의 높이가 스택의 맨 앞부분의 블록의 높이보다 더 높은 경우 입니다.
Function Solution(A: Array of Integer, W: Integer, H: Integer)
S: Stack of Integer
x <- 0
for i := 0 to W-1 do
while (!S.empty()) and (A[S.front()] < A[i]) do
// do something
endWhile
S.push(i)
endFor
return x
endFunction
3번 인덱스의 블록의 높이가 2번 인덱스 보다 높습니다. 범위가 0 ~ 3일 경우, 채워지는 빗물의 양은 위의 그림과 같습니다. 이 빗물의 양을 구해야 합니다.
스택이 비거나, 스택의 맨 앞의 값이 3번 인덱스 높이보다 더 높을 때 까지 계속 값을 꺼냅니다. 우선 맨 앞의 값인 2번을 꺼냅니다.
Function Solution(A: Array of Integer, W: Integer, H: Integer)
S: Stack of Integer
x <- 0
for i := 0 to W-1 do
while (!S.empty()) and (A[S.front()] < A[i]) do
top := S.push()
if S.empty() then break
endWhile
S.push(i)
endFor
return x
endFunction
2번을 스택에서 꺼내서 top이라는 변수에 대입했습니다. 하지만 바로 2와 3의 높이 차를 계산하지 않습니다. 스택에서 한 번더 꺼내 top으로부터 왼쪽의 위치를 파악합니다. 이 부분의 블록의 높이가 3 위치의 높이보다 더 작을 경우, 왼쪽의 높이와 3번째 인덱스의 블록 높이 차이가 빗물의 높이가 됩니다. 이를 Min(A[i], A[S.front()]) - A[top] 으로 표현할 수 있습니다.
너비의 경우 파란색 인덱스에서 보라색 인덱스의 차이의 1을 더 빼면 됩니다. 즉 i - S.front() - 1 이 됩니다.
Function Solution(A: Array of Integer, W: Integer, H: Integer)
S: Stack of Integer
x <- 0
for i := 0 to W-1 do
while (!S.empty()) and (A[S.front()] < A[i]) do
top := S.push()
if S.empty() then break
depth <- Min(A[i], A[S.front()]) - A[top]
width <- i - S.front() - 1
x <- (x + depth * width)
endWhile
S.push(i)
endFor
return x
endFunction
이렇게 해서 위와 같이 솔루션 코드가 완성되었습니다. 솔루션 코드가 제대로 작동하는 지 확인하기 위해 해당 이미지로 다시 이동합니다.
i가 3일 경우 입니다. 이 때 top값은 스택에서 pop한 값이므로 2가 됩니다. 그 다음 스택에 남아 있는 값중 가장 맨 앞에 있는 값이 1이 됩니다.
높이의 경우 A[1], A[3]중 A[1]이 작기 때문에 depth는 A[1] - A[2]이 됩니다.
너비의 경우 3 - 1 - 1 이므로 값은 1이 되므로 x에 A[1] * 1, 즉 0을 추가하게 되어 x의 값은 0이 됩니다.
top값은 1이 되고, 스택에 남아있는 값은 0이 됩니다.
높이의 경우 A[0] > A[3]입니다. 따라서 A[3] - A[1]이 됩니다.
너비의 경우 3 - 0 - 1이므로 2가 됩니다.
따라서 x에 2 * A[3]의 값이 추가되어 총 2가 됩니다.
인덱스 0의 높이는 3보다 더 높기 때문에 특정 작업을 중단하고 3을 스택에 추가합니다.
3을 스택에서 꺼내 top에 저장합니다.
높이는 A[4]와 A[0]중에 A[4]가 더 낮으므로 A[4] - A[3]이 됩니다.
너비는 4 - 0 - 1이므로 3이 됩니다.
따라서 x에 1 * 3이 추가되어 총 5가 됩니다.
마지막에는 top = 4, 높이는 A[5] - A[4] = 1, 너비는 5 - 0 - 1 = 4로 4가 추가되고
x의 총합은 9가 됩니다.
위의 풀이보다 스택의 풀이가 4배 가량 더 빠릅니다.
마치며
브루트 포스 방법에 비해 스택을 사용하는 방법이 아이디어를 내기가 훨씬 까다롭습니다. 하지만 스택 풀이의 핵심은 블록을 순회하면서 새로운 블록을 받아들일 때마다 빗물의 양을 갱신하는 것입니다. 이것만 생각한다면 스택 풀이에 어려움이 그나마 해소되리라 생각합니다.
