[백준] 10799번 쇠막대기

문제

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

풀이과정

스택을 사용하는 대표적인 문제 중 하나이다.

입력은 문자열을 이용하여 받았고, 문자열의 길이만큼 반복문을 통해서 괄호를 체크하였다.

문제의 핵심은 '()'가 나올 때 '('의 개수를 체크하는 부분인 것 같다. (레이저로 떨어지는 쇠막대기의 개수를 파악할 수 있다.)

'('를 만나면 스택에 push 해주고 ')'를 만날 경우에는 두 가지 경우로 나누어서 처리했다.

1. ')' 만날 경우 바로 이전의 index의 문자가 '('인 경우에는 레이저이기 때문에 '('를 pop 시켜주고 '('의 개수를 파악해준다.

2. ')' 만났지만 바로 이전의 index의 문자가 '('가 아닌 경우에는 쇠막대기의 끝이기 때문에 1만 더해준다.

소스코드

#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
 
int main()
{
    int ans=0;
    string input_bracket;
    stack<int> bracket_stack;
 
    cin >> input_bracket;
 
    int n = input_bracket.length();
 
    for (int i = 0; i < n; i++)
    {
        if (input_bracket[i] == '(')
        {
            bracket_stack.push(i);
        }
        else
        {
            if (bracket_stack.top() + 1 == i)
            {
                bracket_stack.pop();
                ans += bracket_stack.size();
            }
            else
            {
                bracket_stack.pop();
                ans += 1;
            }
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}