[14719] 빗 물 - 스택/투 포인터/구현 ★★★☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/14719

 

14719번: 빗물

---

[ 문제 접근 ]

 

역시 monotone Stack 문제 중 하나이다.

이런 구현 문제는 글로 남겨 놓기가 힘들다. 그냥 다시 풀어 보는게 최고다.

 

풀이는 Stack을 이용한 풀이가 있고, 그냥 구현 풀이가 있다. 

두 가지 방법을 전부 해봤다.

 

특히 스택은.. 구현하느라 욕봤다..  반례 질문도 하고, 샷건도 몇번 쳤다.

 

우선 Stack을 이용한 풀이이다. 

 

자세한 레퍼런스는 어떤 중국인 글에서 찾았다.  ( 번역된 페이지 같은데 주석은 중국말로 되어있다. )

 

ref ::  https://www.codetd.com/ko/article/11971611

[데이터 구조] Monotonic Stack - 코드 세계

 

중요 포인트는 이거다.

 

Stack에 블록 높이를 집어 넣으면서 높은 블록이 나오면 그 차이를 이용해서 빗물 answer 를 + 해 나가는 것이다.

 

기존의 monotone Stack 보다. 디테일한 구현이 들어간다.

 

 

---

[ 최종 코드 ]

 

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

using std::cout; using std::cin;
using std::vector;

int H, W;
int answer;

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	std::stack<int> st;
	cin >> H >> W;

	int max = 0;

	while (W--) {
		int h;
		cin >> h;
		
		int cnt = 0;
		while (!st.empty() && st.top() < h) {

			// 여기에 들어온 스택 원소들은 pop하고 다시 채워 놓을거 없이 버려도 된다. 
			if (h > max && st.top()<=max) {  
				answer += max - st.top();
				st.pop();
			
			}
            // 빗물을 계산하고 높이 h 만큼 다시 스택에 쌓는다. ( Key Point )
			else {
				answer += h - st.top();
				st.pop();
				cnt++;
			}
		}
		if (cnt) {
			for (int i = 0; i < cnt; i++) {
				st.push(h);
			}
		}

		max = std::max(max, h);  // 왼쪽 최고 값.
		st.push(h);

	}
	cout << answer;

	return 0;
}

 

[ 다른 풀이 ]

 

백준 질문하기에 어떤 분이 답변으로 쓴 글이다.  

11 3 4 5 3 4 5 3 4 5 7이 들어왔다고 쳐 봅시다.

그러면
11 [3] 4 5 3 4 5 3 4 5 7
에서 [3]에는 몇 만큼의 물이 차야 할까요?

[3]의 왼쪽에 있는 것 중 제일 큰 높이를 가지는 건 11입니다.
오른쪽에 있는 것 중에서 제일 큰 높이를 가지는 건 7이네요.

따라서, [3]에는 7만큼의 물이 채워집니다.
이렇게 생각하면 코드가 짧아지고 매우 간결해집니다.

 

구글링 해보니 생각보다 이렇게 푼 사람들이 많았다.

 

https://bbeomgeun.tistory.com/148

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

---

[ Key Point ]

 

👉 answer을 h와 top() 의 차이로 계산한 노드들은 pop 하고 다시 h 만큼의 값으로 스택에 넣어준다.

 

👉 풀다가 테스트 케이스 다 통과되길래 제출 했는데 역시 실패.. 반례가 생각이 안나 질문하기에 질문도 남겼다.

어느 고수분이 바로 답변 주셔서 그거 가지고 코드 고치고 다시 풀 수 있었다.

---

[ 다른 사람 풀이 ]

 

ref :: https://hwan-shell.tistory.com/276