문제

5875번: 오타

풀이

괄호의 종류에따라 -1, 1로하여 그 누적합을 구하면 현재 문자열의 괄호쌍이 올바른지 아닌지 판단할 수 있다.
이를 응용하여 누적합으로 문제를 해결할 수 있다.
문자열 중 틀린 괄호의 개수가 1개 이므로 문자열의 괄호쌍은 항상 0개, 2개 차이가 난다.
만약 (괄호가 더 많다면 오른쪽부터, )괄호가 더 많다면 왼쪽부터 누적합을 계산한다.
예를 들어 (=1, )=-1로 두고 누적합을 계산할 수 있다.
총 누적합의 값이 0이라면 올바른 괄호, 2라면 (의 수가 더 많고, -2라면 )의 수가 더 많다는 뜻이 된다.

문제의 예시를 이용하여 풀어보면 입력으로 ()(())))가 주어질때 )의 개수가 더 많으므로
왼쪽부터 누적합을 한다면 {1, 0, 1, 2, 1, 0, -1, -2}가 된다.
이때 올바른 괄호쌍이라면 누적합에 -1이라는 값이 생길 수 없고 이를 없애기 위해서 -1이 발생한 지점을 포함한 누적합 계산 앞부분의 ) 괄호 중 하나를 반대로 바꾸면 해결할 수 있다.
즉 -1이 발생한 지점을 포함하여 그 앞부분의 )의 개수가 답이 된다.

만약 (이 더 많다면 오른쪽부터 누적합을 계산하고 -1이 아닌 반대로 1이 발생한 지점을 기준으로 계산하면 된다.

괄호가 수정될 때 2만큼의 차이를 발생시킨다. 이를 통해서 최종 누적합을 0으로 만들기 위한 작업인데, 왼쪽부터 누적합을 계산할때 올바른 괄호쌍이라면 음수가 절대 발생해서는 안된다. 아무리 많이 괄호가 열려도(+1) 나중에 그 괄호를 닫으면(-1)되니까 이 경우에 양수로 커져도 괄호가 잘못되었는지 알 수 없지만, 열린 괄호보다 닫는 괄호가 많아지면 그 순간(누적합이 음수가 되는 순간) 잘못된 괄호라는 것을 알 수 있게된다. 이 음수가 발생한 원인을 제거하기 위해 음수가 발생한 지점부터 처음까지 중 닫는 괄호 하나를 여는 괄호 하나도 바꾸면 된다.
문제에서 잘못된 괄호가 하나임을 알려주었기에 해결할 수 있는 방법이다.

누적합이 음수가 되는 경우를 스택의 언더플로우가 발생하는 경우로 대입해서 해결할 수도 있다.

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string input;
    int answer = 0;
    cin >> input;
    vector<int> number(input.size());
    vector<int> accRight(input.size());
    vector<int> accLeft(input.size());
    for (int i=0; i < input.size(); i++){
        if (input[i] == '(') number[i] = 1;
        else number[i] = -1;
    }
    accRight = number;
    accLeft = number;
    for (int i=1; i < input.size(); i++){
        accLeft[i] += accLeft[i-1];
        accRight[input.size()-i-1] += accRight[input.size()-i];
    }
    if (accLeft[accLeft.size()-1] == -2){
        for (int i=0; i<input.size(); i++){
            if (input[i] == ')')
                answer++;
            if (accLeft[i] == -1 ){
                break;
            }
        }
    }
    else if (accLeft[accLeft.size()-1] == 2){ // 오른쪽부터 누적합을 계산
        for (int i=0; i<input.size(); i++){
            if (input[input.size()-i-1] == '(')
                answer++;
            if (accRight[input.size()-i-1] == 1){
                break;
            }
        }
    }
    cout << answer << endl;
    return 0;
}