5875 오타

처음에 30분동안 고민하다가 안 풀려서 실패...

그러곤 마지막에 바로 아이디어가 떠올라서 해결했다

 

---

먼저 오타가 최대 한 번 났기 때문에 

1. '(' 와 ')'개수가 일치하는 경우

2. '(' 가 더 많은 경우

3. ')' 가 더 많은 경우

3가지 경우로 나눌 수 있다.

 

1. 의 경우 미리 판단해서 0을 리턴하면 된다

2.의 경우는 문자열을 뒤집으면 3.의 경우와 같아진다

그러므로 3.의 경우만 고려하자

 

 

먼저 ')' 가 더 많은 경우 결국 올바른 괄호 쌍을 만들어주려면 ')'를 '('로 변환해야 한다

그럼 어떤 ')' 를 바꿔줄지 고민하면 되는데.......

위의 그림처럼 닫을 수 없는 ')'가 생겨난 이후부터 )를 (로 변환할 수 없다 

그래서 닫을 수 없는 괄호가 나타나는 시점까지 )의 개수를 세면 된다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include<cassert>
#include <climits>
#include <tuple>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int main() {
    string s;
    cin >> s;
    
    int left = 0, right = 0;
    
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(')
            left++;
        else
            right++;
    }
    
    if (left == right) {
        printf("0\n");
        return 0;
    }
    
    string revertString = "";
    if (right < left) {
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] == '(')
                revertString += ')';
            else
                revertString += '(';
        }
        
        s = revertString;
        int tmp = left;
        left = right;
        right = tmp;
    }
    
    // cout << s << "\n" << left << " " << right << "\n";
    
    stack<char> st;
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            st.push('(');
            continue;
        }
        
        ans++;
        if (st.size() == 0)
            break;
        st.pop();
    }
    
    printf("%d\n", ans);
    
    return 0;
}