백준 14719번: 빗물

[문제 링크]

14719번: 빗물

---

은근히 까다로운 구현 문제였다.

2차원 세계 바깥쪽은 블록이 없기 때문에 빗물이 고이지 않는다. 따라서 첫번째와 마지막 블록의 높이가 중요하다고 볼 수 있다. 

필자는 주어진 배열에서 블록의 높이가 가장 높은 인덱스를 찾은 다음, 양 끝을 시작점으로 하여 두개의 포인터가 높이가 가장 높은 인덱스를 향해 가도록 구현하였다.

---

#include <iostream>
#include <queue>
using namespace std;

int H, W;
int block[501];

int getHighestIndex() {
	int highest = block[0];
	int idx = 0;

	for(int i=1; i<W; i++)
		if (highest <= block[i]) {
			highest = block[i];
			idx = i;
		}

	return idx;
}

int getRainWater() {
	queue<int> qFront, qBack;
	int highIdx = getHighestIndex();
	int frontHigh = 0, backHigh = 0;
	int ret = 0;

	for (int i = 0; i < W; i++) {
		int front = i;
		int back = W - 1 - i;

		if (front <= highIdx) {
			if (frontHigh > block[front]) {
				qFront.push(block[front]);
			}
			else {
				while (!qFront.empty()) {
					ret += frontHigh - qFront.front();
					qFront.pop();
				}
				frontHigh = block[front];
			}
		}

		if (back >= highIdx) {
			if (backHigh > block[back]) {
				qBack.push(block[back]);
			}
			else {
				while (!qBack.empty()) {
					ret += backHigh - qBack.front();
					qBack.pop();
				}
				backHigh = block[back];
			}
		}
	}

	return ret;
}

int main(void) {
	cin >> H >> W;

	for (int i = 0; i < W; i++)
		cin >> block[i];

	cout << getRainWater() << endl;

	return 0;
}