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

문제 링크

10799번: 쇠막대기

 

풀이

스택 응용 문제

1. i가 str.size()-1이 아니라면 레이저인지 체크한 뒤, 레이저라면 answer에 현재 스택에 있는 막대기의 수를 더해준다. ()가 한 세트이기 때문에 i++도 해준다.
2. (라면 stk에 push한다.
3. )라면 stk에서 pop하고, answer에 1을 더해주는데, 예를 들어 막대기가 두 개의 레이저로 인해 잘렸다면 레이저 수 + 1로 3등분 되기 때문에 이를 위한 계산이다.

 

코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;

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

    string str;
    cin >> str;

    int answer = 0;
    stack<char> stk;

    for (int i = 0; i < str.size(); i++)
    {
        if (i != str.size() - 1 && str[i] == '(' && str[i + 1] == ')')
        {
            answer += stk.size();
            i++;
        }
        else if (str[i] == '(')
        {
            stk.push(str[i]);
        }
        else if (str[i] == ')')
        {
            stk.pop();
            answer++;
        }
    }

    cout << answer;
}