#10799 쇠막대기

# 문제

# 입력 및 출력

# 풀이

처음엔 레이저 부분인 ()를 .으로 치환해서 풀 생각이었다

// 틀린 풀이
#include <iostream>
#include <string>
using namespace std;

int main() {
	string str;
	cin >> str;
	int cnt = 0, stick = 0;
	while (str.find("()") != string::npos) { // ()부분 .으로 치환
		int index = str.find("()");
		str.replace(str.begin() + index, str.begin() + index + 2, ".");
	}
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			stick++;
			cnt++;
		}
		if (str[i] == '.') cnt += stick;
		if (str[i] == ')') stick--;
	}
	cout << cnt;
}

치환하는 부분에서 문자열 길이가 자꾸 바뀌기 때문에 str.begin()을 써줘야 문제가 안생김

https://wendys.tistory.com/8

[C/C++] string replace all 문자열 모두 치환

 

지금 보니까 알고리즘 자체도 잘못된 것 같다ㅋㅋㅋ

(일때 더하는 게 아니고 )일때 더해야하는데,,

 

아무튼 이렇게 푸니까 시간 초과가 뜨길래 cin cout문젠가 싶어서

ios::sync_with_stdio(false); 도 넣어서 돌려봤는데 그래도 시간초과가 뜨더라

 

문자열의 최대 길이가 100,000이다보니 ()가 많아질수록 while문이 많이 돌아서 시간초과가 뜬 것 같다

 

그래서 아래는 stack을 사용했음

#include <iostream>
#include <string>
#include <stack>
using namespace std;
stack<int> s;

int main() {
	string str;
	cin >> str;
	int cnt = 0;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			s.push('(');
		}
		if (str[i] == ')') {
			s.pop();
			if(str[i-1]=='(') cnt += s.size();
			else cnt++;
		}
	}
	cout << cnt;
}

(이면 스택에 넣어주고 )이면 pop해줌

대신 레이저 부분인 ()이라면 막대기 개수(스택에 들은)만큼 더해주고

레이저 부분이 아니라면 그냥 막대기 끝이므로 1개만 더해줌

 

입출력 예제 2번의 그림은 다음과 같음

근데 굳이 스택없이도 될 것 같음

막대기 개수만 저장해두면,, 상관이 없을 것 같음

 

#include <iostream>
#include <string>
using namespace std;
int main() {
	string str;
	cin >> str;
	int cnt = 0, stick = 0;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			stick++;
		}
		if (str[i] == ')') {
			stick--;
			if (str[i - 1] == '(') cnt += stick;
			else cnt++;
		}
	}
	cout << cnt;
}

스택 안써도 잘 돌아감