10799_쇠막대기

▶실버2

문제

풀이

stack 이용

'()' => 레이저

제일 위에 있는 막대기는  ')' 가 나오기 전까지 레이저로 자를 수 있음

※ 막대가 끊겨도 레이저를 쏘면 한 조각으로 치기 때문에 ')' 이 나온다고 해서 무작정 pop하면 안됨

즉,

1 : '('는 push 하고,

2 : ')'일 경우 레이저인지 쇠 막대기인지 확인 후

2-1: 쇠 막대기면 cnt(쇠 막대기의 오른쪽 끝 점 개수) 증가

2-2: 레이저이면 stack의 크기(쇠 막대기의 왼쪽 끝 점 개수)만큼 더한 후, cnt(쇠 막대기의 오른쪽 끝 점 개수) 만큼 pop해준 후 cnt 초기화

3: 반복문 다 돌린 후 마지막으로 cnt 더해 줌

코드

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

stack <char> tree;
int main() {
	string str;
	cin >> str;

	int ans = 0;
	int cnt = 0;
	for (int i = 0; i < str.length(); i++) {
		
		if (i == 0) {
			tree.push('(');
			continue;
		}
		if (str[i] == '(') {
			tree.push('(');
		}
		else {
			if (str[i - 1] == '(') {
				tree.pop();
				ans += tree.size();
				for (int j = 0; j < cnt; j++) {
					tree.pop();
				}
				cnt = 0;
			}
			else {
				cnt++;
			}
		}
	}
	ans += cnt;
	cout << ans;
}