백준 6198번 옥상 정원 꾸미기 - 모노톤 스택

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

 

https://www.acmicpc.net/problem/17298의 하위호환

 

아이디어:

1. 모노톤 스택 사용

스택에는 2가지 문제 유형이 있는데, 첫번째는 괄호 지우는 것처럼 자연스러운 패턴을 찾는 것

2번째는 6198번과 모노톤 스택처럼 스택 내부의 정렬(?)이다.

https://www.youtube.com/watch?v=Z4R582bn7B8

2. 목표는 빌딩을 볼 수 있는 횟수의 총합

3. 스택의 입력은 빌딩의 높이인데, 이걸 내림차순으로 정렬해서 더 낮은 값이 있으면 pop하는 로직이 필요하다.

4. 첫 빌딩 높이는 그냥 push

5. 다음 들어오는 빌딩부터

만약, 스택 top이 입력 빌딩보다 작으면 pop하고 크거나 같으면 정답에 더한 뒤, 스택에 push한다.

(ex. 백준 예제의 경우, 10, 3, 7, 4 12, 2에서

10 입력 > 스택: [10]

3 입력 > 스택: [10]로 answer 1 추가, 3 push

7 입력 > 스택: [10, 3]에서 7은 3보다 크므로 3 pop, 10보다 작으므로 answer 1 추가, 7 push

4 입력 > 스택: [10, 7]로 answer 2 추가, 4 push

12 입력 > 스택: [10, 7, 4]에서 12보다 작은 숫자 pop, 12 push

2 입력 > 스택: [12]로 answer 1 추가, 2 push)

 

// 6198

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

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, h;
	long long answer = 0;
	cin >> N;
	vector<int> building(N, 0);
	stack<int> myStack;

	for (int i = 0; i < N; i++) {
		
		cin >> h;

		if (myStack.empty()) {
			myStack.push(h);
			continue;
		}

		while (!myStack.empty() && myStack.top() <= h) {
			myStack.pop();
		}
		answer += myStack.size();
		myStack.push(h);

	}

	cout << answer;

	return 0;
}

---

풀이 간소화

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	long long int N, tmp, ans = 0;
	stack<long long int> S;
	cin >> N;

	while (N--) {
		cin >> tmp;

		while (!S.empty() && S.top() <= tmp) {
			S.pop();
		}

		ans += S.size();
		S.push(tmp);

	}

	cout << ans;

	return 0;

}

 

위 과정을 그대로 옮긴다.

입력이 10 3 7 4 12 2 일때 스택 S와  S.size()를 추적해보면

입력: 10 스택 S: (empty) S.size(): 0

입력: 3 스택 S: 10 S.size(): 1

입력: 7 스택 S: 10 S.size(): 1

입력: 4 스택 S: 10 7 S.size(): 2

입력: 12 스택 S: (empty) S.size(): 0

입력: 2 스택 S: 12 S.size(): 1

 

S.size()가 볼 수 있는 정원의 갯수를 유지한다는 점이 중요