[백준 11899] 괄호 끼워넣기

🔗알고리즘 문제

학교 자료구조시간에 풀었던 스택문제와 굉장히 비슷한 방식으로 해결할 수 있어 어렵지 않았던 문제이다.

문제 분석

이 문제는 한마디로 올바르지 않은 괄호열이 주어졌을 때 올바른 괄호열로 만들기 위해 추가 괄호가 몇개 필요한지 구하는 문제이다.

발상

괄호를 보자마자 아 ! 이 문제는 스택이다 라는생각을 하였다. 주입식 교육의 옳게된 예...

괄호를 하나하나 스택에 담아주고 올바른 괄호가 담기면 스택에서 제외시켜준다. 모든 문자열을 스택에 담고난 후 스택에 남아있는 것은 올바르지 않은 괄호의 수이고 그것이 필요한 괄호의 수와도 동일하다.

알고리즘 설계

1. 괄호열을 입력받는다.
2. 괄호열을 반복문을 돌며 해당 괄호를 스택에 집어넣는다. 이때 올바른 괄호가 들어오게 되면 스택에서 값을 뺀다.
3. 스택의 사이즈를 출력한다.

코드

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main(){
    stack<int> stack;
    string input;
    cin >> input;

    for(int i = 0; i < input.length(); i++){
        if(stack.empty() == false && stack.top() == '(' && input[i] == ')'){
            stack.pop();
        }
        else{
            stack.push(input[i]);
        }
    }

    cout << stack.size();
}