[백준] 10799 쇠막대기

문제 설명

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

10799번: 쇠막대기

여러개의 쇠막대기가 있고 이를 레이저로 절단하면, 잘려진 쇠막대기의 조각의 개수를 구하기

• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ()으로 표현됨
• 쇠막대기의 왼쪽 끝은 여는 괄호 (, 오른쪽 끝은 닫힌 괄호 )로 표현

 

문제 풀이법

스택을 사용하면은 금방 풀 수 있다

• 우선 '(' 가 나오면 스택에 '('를 push
• 레이저가 나오면 '()' 스택을 pop한 후 stack의 size를 더한다
• 이전 글자가 '(' 가 아닌, 즉 레이저가 아닌 ')'가 나오면 자투리이므로, 스택을 pop한 후 + 1 한다

 

소스 코드

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    stack<char> s;
    string str;
    int cnt;
    
    cin >> str;
    cnt = 0;
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == '(')
            s.push('(');
        else if (str[i] == ')' && str[i - 1] == '(')
        {
            s.pop();
            cnt += s.size();
        }
        else
        {
            s.pop();
            cnt++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}