[백준(BOJ) 10799번] 쇠막대기 (C++)

문제 링크

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

 

문제 정보

입력

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다. 

출력

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

 

풀이

 생각이 어려웠고 구현은 쉬웠던 문제였다. 여는 괄호는 스택에 push 해주고 닫는 괄호일 때 바로 앞에 괄호가 여는 괄호인지, 닫는 괄호인지를 통해 레이저와 쇠 막대기의 끝을 구별하면 된다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string str;
	cin >> str;
	
	stack<char> S;
	
	int ans = 0;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') { // 여는 괄호
			S.push(str[i]);
		} else { // 닫는 괄호
			if (str[i - 1] == '(') { // 레이저일 경우
				S.pop(); // 쇠 막대기로 착각하고 앞에서 스택에 여는 괄호를 하나 추가했으므로 pop 한다.
				ans += S.size(); // 쇠 막대기의 개수만큼 조각이 잘린다. 
			} else { // 쇠 막대기의 끝일 경우
				S.pop(); // 막대가 끝났으므로 막대기 하나 제거(여는 괄호 제거)
				ans++; // 쇠 막대기의 끝(오른쪽) 조각을 더해준다.
			}
		}
	}
	
	cout << ans;
	
	return 0;
}