BOJ - 10799번_쇠막대기

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램 작성하기

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.

• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.

• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.

• 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

풀이

C++ STL stack을 이용하여 여는 괄호가 나오면 스택에 추가한다.

닫힌 괄호가 나왔을 때, 바로 이전의 문자가 열린 괄호라면 레이저이고 닫힌 괄호라면 쇠막대기의 끝점이다.

레이저가 나오면 현재 스택 size가 잘려진 조각 개수가 된다. 추가적으로, 쇠막대기의 끝점이 나오면 조각 개수를 1 더한다.

소스코드

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	getline(cin, s);
	
	stack<char> st;
	int cnt = 0;
	for(int i=0; i<s.size(); i++) {
		if(s[i]=='(') {
			st.push(s[i]);
		}
		else if(s[i]==')' && s[i-1]=='(') {
			st.pop();
			cnt += st.size();
		}
		else {
			cnt++;
			st.pop();
		}
	}
	cout << cnt;
}