[baekjoon 14719] 빗물 (구현, 스택) (C++)

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

14719번: 빗물

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

이런 식으로 빗물이 고인다. 

 

아이디어를 찾는다면 나름 쉽게 풀 수 있다.

 

1. 시뮬레이션, 구현

 

5 4 3 5 6 8 7 1 이 있다고 치면 빗물은 좌, 우에 쌓일 것이다. 그러므로 4부터 계산을 해주는데

4는 5와 8 사이에 있고 틈에 총 1만큼 쌓일 것이다.

3은 5와 8 사이에 있고 틈에 총 2만큼 쌓일 것이다.

5, 6, 8, 7, 1은 빗물이 쌓이지 못한다.

 

즉, 현재 나의 위치의 왼쪽과 오른쪽에서 가장 큰 수와 나를 비교해서 두 수 보다 작으면, min(left, right) - 나 만큼 빗물이 찬다는 뜻이다.

아이디어를 잘 찾았다면 구현은 쉬울 것이다.

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

stack<int> st;
int x, y, arr[501];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> x >> y;
	for (int i = 0; i < y; i++) {
		cin >> arr[i];
	}
	int answer = 0;

	for (int i = 1; i < y; i++) {
		int left = *max_element(arr, arr + i);
		int right = *max_element(arr + i + 1, arr + y);
		int cur = arr[i];
		if (cur < left && cur < right) {
			answer += min(left, right) - cur;
		}
	}
	cout << answer;
}

 

2. 스택

 

난 처음에 스택을 이용해서 풀었는데, 식이 꽤나 복잡해졌다.

간단하게 설명하면, 스택의 내부는 top으로 갈수록 작거나, 같도록 유지해주었다.

그리고 top보다 큰 수가 들어오면 pop 해주면서 더해주었다.

 

3 0 1 이 들어오면 스택은 3이 들어오고, 0이 들어오고 (top이 더 작으므로 push)

이후 1이 들어오면(top보다 크므로 차이만큼 더해준다.) 1-0만큼 더해주었다.

 

하지만 이렇게 pop 하고 끝내버린다면 3 0 1 4의 경우 3과 4 사이에 총 5만큼 쌓여야 하는데

0이 pop 되었으므로 0에 해당하는 추가 depth 2를 더해주지 못한다.

따라서 난 pop 한 만큼 개수를 세서 다시 업데이트해서 넣어주었다.

 

3 0 1 4에서 1을 만났을 경우, top은 0이므로 pop해준 뒤 pop 한 개수만큼 1을 넣어준다.

즉, 더해준 만큼 틈을 채워준다고 생각하면 된다.

그러면 스택 내부는 3 1 1이 되어있을 것이고, 그때 4를 만나면 3을 만날 때까지 3-1, 3-1이 더해져서 총 5가 된다.

위에서 왜 4-1이 아니고 3-1을 했냐 하면 분기를 나눠줘야 하기 때문이다.

 

0. 스택에 수를 쌓으면서 최댓값을 저장해준다. (3 0 1의 경우 3을 최댓값으로 기억하고 있자)

1. top보다 수가 적으면 push

2. top보다 수가 크면 

2-1. 만약 들어오는 수가 최대와 같다면

=> 최대 높이 사이의 수들에 대해서 계산을 해준다 3 0 1 3이면 0 1에 해당, 그리고 0 1을 3만큼 채웠으므로 3 3 3 3

2-2. 만약 들어오는 수가 최대보다 크다면

=> 최대 높이 사이의 수들에 대해서 계산을 해준다 3 0 1 4면 0 1에 해당, 그리고 4보다 작으므로 3 0 1은 더 이상 틈을 채울 수 없으므로 그냥 pop 해준다. (이후의 높이는 4에 맞춰서 계산되므로)

2-3. 만약 들어오는 수가 최대보다 적다면

=> 들어오는 수보다 작은 수를 만날 때까지 수를 처리해준다. 3 0 1 2면 0 1에 해당, 3 2 2 2 가 된다.

 

#include <iostream>
#include <stack>

using namespace std;

stack<int> st;
int x, y, arr[501];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> x >> y;
	for (int i = 0; i < y; i++) {
		cin >> arr[i];
	}

	int limit = 0, answer = 0;
	for (int i = 0; i < y; i++) {
		int height = arr[i];
		if (st.empty()) { // 제일 처음 초기화 과정
			st.push(height);
			limit = max(limit, st.top());
		}
		else {
			if (height <= st.top()) { // top보다 작거나 같으면 그냥 push
				st.push(height);
			}
			else { // height이 st.top() 보다 크면
				if (height == limit) { // 그때 현재 수가 이제까지의 최대와 같으면 
					int cnt = 1;
					while (st.top() != height) { // 최대까지 가면서 그 차이를 더해준다.
						cnt++;
						answer += height - st.top();
						st.pop();
					}
					for (int i = 0; i < cnt; i++) // 틈을 채운 수로 업데이트
						st.push(height);
				}
				else if (height > limit) { // 현재 수가 최대보다 크면
					while (st.top() < height) { // 현재 수보다 작은 수는 다 빼준다.
						answer += limit - st.top(); // 차이는 최대와 st.top
						st.pop();
						if (st.empty())
							break;
					}
					limit = height; // 현재 수보다 작은 수를 다 빼줬으므로 새롭게 갱신해준다.
					st.push(height);
				}
				else { // height이 limit 보다 작으면
					int cnt = 1; // 기본 height 넣을 갯수
					while (st.top() < height) {
						cnt++;
						answer += height - st.top();
						st.pop();
					}
					for (int i = 0; i < cnt; i++)
						st.push(height);
				}
			}
		}
	}
	cout << answer;
}

스택 풀이는 해로운 것 같다.. 코드를 보고도 이해가 될까 싶긴 하다.