올바른 괄호

알고리즘 구분 : 누적 합

문제

 $\texttt{(}$, $\texttt{)}$로 구성된 문자열 $S$에서 정확히 하나의 괄호를 지워 올바른 괄호열을 만들 수 있는 경우의 수를 출력하자.

올바른 괄호열은 다음과 같이 정의된다.

 $\texttt{()}$는 올바른 괄호열이다.
$\texttt{A}$가 올바른 괄호열이면 $\texttt{(A)}$는 올바른 괄호열이다.
$\texttt{A}$와 $\texttt{B}$가 올바른 괄호열이면 $\texttt{AB}$는 올바른 괄호열이다.
입력
첫번째 줄에 문자열 $S$가 공백 없이 주어진다. ($3 \leq \vert S \vert \leq 100\,000$, $\vert S \vert$는 홀수이다.)

답은 $1$ 이상이다. 즉, 지웠을 때 올바른 괄호열이 되는 문자가 적어도 하나 존재한다.

출력
올바른 괄호열을 만들 수 있는 경우의 수를 출력한다.

예제 입력 1
()(()
예제 출력 1
2
예제 입력 2
()(()))
예제 출력 2
4

문제 풀이

이 문제는 SUAPC 2022 Winter에 출제되었던 문제다. 아직 글을 작성하지는 않았지만, 당시 나는 SUAPC에 참가하여, 이 문제를 풀려고 계속 노력했지만, 결국 풀지 못하고 나온 문제였다. SUAPC 당시의 문제를 어떻게 접근하고자 했었는지부터 다루어보고자 한다.

1. 대회 당시
   괄호 문제에 대표적인 알고리즘이 있다. 바로 '스택'이다. 이 문제를 보자마자 팀원들과 스택으로 접근해서 풀 수 있을 것 같다고 판단하여 바로 구현을 진행하였다. 그러나 시간초과를 받았었다. 시간초과를 받게 된 원인을 간단하게 판별해보자면, 결국 문제에서 하나의 괄호가 없을 때 전체 괄호가 올바르게 되는지를 확인하는 과정을 전 범위에서 진행을 해야한다. 내가 제거하게 될 괄호를 선택하는 경우의 수 N과 제거한 이후, 해당 괄호 문자열이 올바른지 순회 탐색하는 N의 시간이 곱해져서 O(N^2)의 시간복잡도를 가지게 된다. 문제에서 문자열의 최대 길이는 100,000이라고 했으므로, 최대 10,000,000,000의 연산을 가지게 되며, 이는 string 자료형의 특성상 1초라는 시간 제한을 만족시킬 수 없게 된다.
   그렇기에, 나는 이 부분을 최대한 가지치기를 통해 해결하고자 하였다. 첫 번째로 '('와 ')'의 괄호 개수를 카운팅하여, 더 많은 카운트를 가진 괄호만 제거하면서 올바른지 여부를 판단하도록 구현하였다. 그럼에도 TLE를 받았었다.

2. 정답을 맞춘 접근법
   위와 같은 사고를 거치고 나서 시간이 꽤 지나고, 다시 이 문제를 풀어보게 되었는데, 문제에서 최소 O(NlogN)이하의 시간복잡도를 가지도록 구현해야 한다고 생각했다. O(N) 즉, 한 번 전체 순회를 통해서 결과를 낼 수 있을 것이라고 판단하고 접근해보았다. 과거 대회 종료 후 문제 해설 당시 들었었던 그룹으로 묶어서 생각해봐야 한다라는 문장이 생각나서 그룹으로 묶는 과정으로 접근해보았다.
   예제를 통해 설명해보자면
   ()(()에서 앞의 ()는 이미 올바른 괄호열 그룹이기 때문에, 해당 부분에서 괄호를 제거할 수 없다. 다음 그룹인, (()에서 이 부분을 확인하는 과정을 거쳐야 한다는 것이다.
   그렇기에, '('와 ')'를 각각 카운팅하며, sum이라는 조건문에 활용할 변수를 하나 더 추가하여 그룹을 관리할 수 있도록 했다. 만약 '('가 나오면 sum++를, ')'가 나오면 sum--를 진행하도록 하였고, 만약 sum == 0이 된다면, 좌 우 괄호의 갯수가 동일해진 괄호열이 완성되었다는 의미이기에, '('카운팅하는 변수를 0으로 초기화하는 과정을 진행하였다. 이 때, ')'를 카운팅하는 변수를 초기화하지 않은 이유는, 괄호열의 시작은 무조건 '('이 담당하게 되고, ')'는 괄호열의 끝을 담당하게 된다. 만약 ')'괄호의 개수가 더 많은 상황일 경우, 시작지점부터 순회하면서 탐색하고 있기에, sum < 0 보다 작아지는 경우가 생겼을 때, ')'의 개수를 출력해야 하기 때문이다. 위의 내용은 2번 예제를 통해 생각해보면 이해가 쉬워진다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

string input;
void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> input;
    
    solve();

    return 0;
}

void solve() {
    int leftCnt, rightCnt, sum;

    leftCnt = 0;
    rightCnt = 0;
    sum = 0;
    for(int i = 0; i < input.length(); i++) {
        if(input[i] == '(') {
            leftCnt++;
            sum++;
        }
        else if(input[i] == ')') {
            rightCnt++;
            sum--;
        }

        if(sum < 0) {
            cout << rightCnt << endl;
            return ;
        }

        if(sum == 0) {
            leftCnt = 0;
        }
    }

    cout << leftCnt << endl;

}

문제 출처 : https://www.acmicpc.net/problem/24552
해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.