[6198] 옥상 정원 꾸미기 - 스택/Monotone Stack ★★★☆ / 복습 ○

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

6198번: 옥상 정원 꾸미기

---

[ 문제 접근 ]

 

그냥 생각 없이 구현하면 시간 초과 나오는 문제.

 

스택 문제라고 해서 스택으로 어떻게 풀어볼까 고민하다가 그냥 GG 치고 다른 사람들의 코드를 봤다.

 

보길 잘한거 같다. 정답 코드를 봐도 이해가 잘 안갔다.

 

결과적으로 이 Monotone Stack을 이해해야 한다.

 

 https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack

monotone stack

 

---

[ 처음 풀이 ]

 

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

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

int N;
std::stack<int> st;
vector<int> arr;
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		arr.push_back(a);
	}
	st.push(arr[0]);
	int sum = 0;
	for (int i = 1; i < N; i++) {
		int idx = i;
		int cur = st.top();
		while (arr[idx] < cur) {  // 마지막 원소 다음 인덱싱 오류.
			st.push(arr[idx]);
			idx++;
			sum += 1;
			if (idx == N)break;
			
		}
		while (!st.empty()) {
			st.pop();
		}
		st.push(arr[i]);
	}
	
	cout << sum;


	return 0;
}

이 코드가 시간 초과 코드이다.

 

입력 받은 빌딩 높이를 전부 벡터 arr 에 넣은 다음,

 

첫번째 빌딩을 나머지 빌딩들 높이와 비교해 가면서 더 높은 건물이 나올때까지 count

스택에 있는 값 전부 버리고,

 

두번째 빌딩을 나머지 빌딩들 높이와 비교해 가면서 더 높은 건물이 나올때까지 count

스택에 있는 값 전부 버리고,

...

---

생각 해보니깐 이렇게 풀면 벡터로 푼거랑 뭐가 다른가 싶다... ( 제발 생각좀 하면서 문제 풀자!!! )

 

스택을 사용한 이유가 없다. 오히려 시간만 더 늘렸을뿐.

cin >> N;
for (int i = 0; i < N; i++) {
	int a;
	cin >> a;
	arr.push_back(a);
}
	
int sum = 0;
for (int i = 0; i < N-1; i++) {
	int max = arr[i];
	for (int j = i + 1; j < N; j++) {
		if (max <= arr[j])	break;
		sum += 1;
    }		
}
	
cout << sum;

---

[ 정답 코드 ]

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

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

int N;
std::stack<int> st;
vector<int> building;
int answer;

void solve() {
	for(int i = 0; i < N; i++) {
		
		while (!st.empty() && st.top() <= building[i]) {
			st.pop();
		}
		st.push(building[i]);
		answer += st.size() - 1;
	}
	cout << answer;
}

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

	cin >> N;
	int size = N;
	while (size--) {
		int a;
		cin >> a;
		building.push_back(a);
	}
	solve();

	return 0;
}

 

다른 사람의 코드를 보니깐 입력을 벡터에 전부 받고 문제를 푸는게 아니라

 

하나씩 입력을 받을때 마다 로직 처리 해준게 있는데 어떻게 이렇게 생각하는지 그 과정이 너무 궁금하다..

 

나는 벡터충이라 문제에 입력만 주어지면 벡터에 넣고 시작해야겠다 밖에 생각이 안나던데....

 

#include <bits/stdc++.h>
using namespace std;

#define ll long long

stack<int> s;
int n;
ll ans;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  ll h;
  while (n--) {
    cin >> h;
    while(!s.empty() && s.top() <= h)
      s.pop();
    s.push(h);
    ans += s.size() -1;
  }
  cout << ans;
  return 0;
}

---

[ Key Point ]

 

👉  answer은 long long 형이여야한다.

 

N이 최대 80,000이고 빌딩의 높이들이 동일하지 않은 상태에서 내림차순으로 주어진다면 정답이 int 형의 범위를 벗어날 수 있기 때문에!

 

구현도 힘든데 아직 이런 디테일을 신경 쓰는게 아직 너무 벅차다. 

 

비슷한 문제로 아래의 문제들이 있다.

 

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

오큰수 : https://www.acmicpc.net/problem/17298

 

 

---

[ 다른 사람 풀이 ]

 

ref :: https://bunnnybin.tistory.com/entry/%EB%B0%B1%EC%A4%80-6198-%EC%98%A5%EC%83%81-%EC%A0%95%EC%9B%90-%EA%BE%B8%EB%AF%B8%EA%B8%B0-C-with-monotone-stack

ref :: https://fisher10001.tistory.com/123

ref :: https://husk321.tistory.com/115