[C++] 백준 10799번 : 쇠막대기

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

10799번: 쇠막대기

---

 문제 풀이

입력받은 string의 크기만큼 반복문을 돈다.

'(' 다음에 바로 ')'에 오면 레이저 처리라는 것이 중요하다.

스택이 비어있거나 string[i]가 '(' 일 경우 '('을 스택에 넣어주고 막대기의 개수를 +1 해준다.

만약 string[i+1]이 ')'라면 레이저 처리하므로 막대기의 개수만큼 조각 수에 추가한다.

레이저 처리일 경우 다다음 인덱스로 넘어가야 하므로 인덱스를 +1 해준다.

string[i]가 ')' 일 경우 막대기의 끝자락이라는 뜻인데,

이 것은 막대기 중 하나가 더 이상 자를 일이 없다는 것을 의미하므로 전체 개수에서 +1 해준다.

 느낀 점

재밌는 스택 문제였다! 막대기의 개수를 보는 것이 중요했던 것 같다.

 코드

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

using namespace std;

stack<char> s;
string input;
int pieces = 0;
int cnt = 0;


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

	cin >> input;
	for (int i = 0; i < input.length();i++) {
		if (s.empty() || input[i] == '(') {
			if (input[i + 1] == ')') {
				pieces += cnt;
				i++;
			}
			else {
				s.push('(');
				cnt++;
			}
		}
		else {
			if (s.top() == '(') {
				cnt--;
				pieces++;
			}
		}
	}

	cout << pieces;
}