괄호 끼워넣기(BOJ11899)

문제

이미지 클릭

문제 설명

• 괄호문자열이 주어 졌을 때 올바른 괄호열을 만들기 위해서 몇 개의 괄호를 추가하여야 하는지 물어보는 문제이다.
• 올바른 괄호열은 (A) , AB (A,B는 올바른 괄호열)의 형태를 만드는 것을 의미한다.

최종 코드

• 문자괄호열과 같은 경우는 스택을 활용한다면 올바른 괄호를 찾을 수 있다.
• 만약 '('괄호가 맨위에 있다면 다음과 같은 작업을 할 수 있다.

( 가 들어왔을 때: (와 (는 올바른 괄호문자열이 아니기 때문에 스택에 넣어준다.
)가 들어왔을 때: (와 )는 올바른 괄호문자열이기 때문에 (를 pop 해준다.

• 위와 같은 방식으로 한다면 결국 올바른 괄호문자열이 아닌 문자들만 남게 되고 결국은 올바른 괄호문자열이 아닌 문자들의 개수만큼 괄호를 추가해 주면 올바른 괄호열이 된다.

#include<bits/stdc++.h>
using namespace std;
stack<char> stk;
int main(){
      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      string s; cin>>s;
      for(auto c:s){
            if(c=='(') stk.push(c); #'(' 가 들어 오면 그대로 넣어준다.
            else {
                  if(!stk.empty()&&stk.top()=='(') stk.pop(); #스택이 비어있지 않고 '('이면 pop
                  else stk.push(c); #아니라면 push
            }
      }
      cout<<stk.size();
}

이미지 클릭