[백준 11899번] 괄호 끼워넣기 (C++)

문제링크 : https://www.acmicpc.net/problem/11899

11899번: 괄호 끼워넣기

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;

    queue<char>q;

    int cnt = 0;

    for(int i=0; i<s.size(); i++)
    {
        if(s[i] == ')' && q.empty())
        {
            cnt++;
            continue;
        }

        if(s[i] == '(')
        {
            q.push(s[i]);
        }

        if(s[i] == ')' && !q.empty())
        {
            q.pop();
        }
    }

    cout << cnt + q.size();

    return 0;
}

큐를 활용하여 풀었다.

 

처음에 큐에 들어가는 값이 ')'이라면 뒤에 '('이 나와도 괄호완성이 안되기에 큐가 비었는데 ')'가 나온다면 넘어가고, 괄호가 필요한건 맞기에 카운트를 증가시킨다.

처음에 큐에 들어가는 값이 '('이라면 큐에 푸쉬해준다.

만약 현재 값이 ')'인데 큐가 비어있지 않다면 큐에 '('이 있다는 것이고 이것은 괄호완성을 의미하기에 큐에 넣었던 '('를 팝해준다.

 

괄호완성이 안되어서 큐에 '('이 쌓인 값과 앞서서 ')'에 대한 카운트를 센 것을 합하여 출력해준다.