[백준 10799] 쇠막대기 (cpp, stack)

🚀  들어가며...

• stack에 '('인 경우의 인덱스를 저장하여 문제를 해결 할 수 있다.

 

🔗  문제

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

10799번: 쇠막대기

 

📑  내용

case 1 : 쇠막대기가 추가되는 경우

"("이 입력되어 쇠막대기 추가되는 경우이다. (stack.push(i))

 

case 2 : 레이저인 경우

")"이 입력되었으며, 이전의 입력이 "("인 경우는 레이저이다 ( ans += stack.size())

 

case 3 : 레이저가 아닌 경우

")"이 입력되었으며, 이전의 입력이 "("이 아니여서 레이저가 아닌 경우 (ans += 1)

 

💌 소스코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main(){
	string str;
	int ans = 0;
	getline(cin,str,'\n');

	int s = str.size();

	stack<int> st;
	for(int i=0; i<str.size(); i++){
		// case 1 : '(' 입력
		if(str[i] == '('){
			st.push(i);
		}
		// )
		else{
			// case 2 : ')' 입력 + 이전 입력이 '('일때 (레이저인 경우)
			if(st.top() == i-1){
				st.pop();
				ans += st.size();
			}
			// case 3 : ')' 입력 (레이저가 아닌 경우)
			else{
				st.pop();
				ans += 1;
			}
		}
	}
	cout << ans << endl;
}