3015번-오아시스 재결합

와...이 문제는 진짜 간단해 보였고 코드도 짰는데 이상할정도로 로직이 이해가 안가서 며칠 답답했음..휴....그래도 좀 감이 잡혀서 코드 작성하고 제출했따....

- c++

#include<iostream>
#include<stack>
#define X first
#define Y second
using namespace std;

int main() {
	int n;
	long long ans = 0;
	cin >> n;
	stack<pair<int, int>> S;
	while (n--) {
		int height;
		cin >> height;
		int cnt = 1;
		while (!S.empty() && S.top().X <= height) {
			ans += S.top().Y;
			if (S.top().X == height)cnt += S.top().Y;
			S.pop();
		}
		if (!S.empty())ans++;
		S.push({ height,cnt });
	}
	cout << ans;

}

- python

n=int(input())
stack=[]
ans=0
for _ in range(n):
    h=int(input())
    cnt=1
    while stack and stack[-1][0]<=h:
        ans+=stack[-1][1]
        if stack[-1][0]==h: cnt+=stack[-1][1]
        stack.pop()
    if stack:ans+=1
    stack.append([h,cnt])
print(ans)

일단 누적할 값은 최대한 빨리 깔끔하게 누적하는 것이 좋고 반복문을 돌며 너무 값을 여러 곳에서 변화 시키면 꼬이게 된다.