[백준 10799번] 쇠막대기 풀이

10799번: 쇠막대기

 

"()"로 표시된 레이저가 쇠막대기를 자를 때 잘린 쇠막대기의 조각수를 구하는 문제이다.

무수히 많은 괄호로 묶여 있는 문제의 형태는 스택을 떠올리면 해결하기 쉽다.

 

이 문제는 문자열을 순회하면서 다음의 케이스를 처리한다.

 

1) '('가 등장할 때

2) ')' 가 등장할 때 - 레이저 표시를 위한 ')' 

3) ')'가 등장할 때 - 열린 괄호를 닫기 위한 ')'

 

1번의 경우에는 스택에 '('를 쌓는다.

 

2번의 경우는 ')' 가 등장 하였을 때, 그 전 인덱스에 '(' 가 있으면 레이저로 판별할 수 있다.  레이저가 등장하였을 때는, 스택에 쌓인 것들 중에서 앞의 레이저 표시를 위해 등장했던 '(' 를 삭제하고 나머지 열린 괄호들의 개수들 만큼 만들어진 조각 수에 추가한다.

 

3번의 경우 ')'가 등장 하였을 때, 그 전 인덱스에 '('가 없으면 이는 열린 괄호를 닫기 위한 ')'라고 판별할 수 있다. 한개의 괄호가 닫혔으므로 스택에서 한개의 '(' 를 제거한다. 스택에는 현재까지 열려있는 괄호의 개수만 남게 되고, 괄호를 닫는 과정에서 한개의 막대 조각이 만들어지므로 만들어진 조각수를 1 증가시킨다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <stack>
using namespace std;

int main() {

    string s;
    cin >> s;

    int re = 0;   
    stack<char> st;
    for (int i=0; i<s.size(); i++) {
        if (s[i] == '(') st.push('(');
        else {
            st.pop();
            if (s[i-1] == '(') re+=st.size();
            else re++;
        }
    }
    printf("%d", re);
    return 0;
}