[백준] 오타

https://www.acmicpc.net/problem/5875

5875번: 오타

문제부터 간단하게 요약하면, 

괄호의 입력이 들어오면, 하나의 문자만 고쳐서 올바른 괄호쌍이 될 수 있는 경우의 수를 출력해야 합니다. 

()(())))

의 input의 경우, 2번째, 5번째, 6번째, 7번째 문자를 고치는 경우에 올바른 문자열이 되므로 4를 출력해야 합니다.

 

<Solution>

기본적으로 괄호와 관련한 문제는 depth를 사용합니다.

(  )  (  )  )  )  ) 의 예시에서 depth를 생각해보면,

1 0 1 0 1 2 3 의 depth가 되는 것을 알 수 있습니다.

 

이 depth를 이용해서 문제를 해결할 수 있는지를 생각해봅시다. 

 

case를 나누어 봅시다.

 

case 1. 오른쪽 괄호 ' ) ' 가 더 많은 경우

이 경우 depth를 구하다 -1이 등장하게 됩니다. 

ex) ()))  depth : 1 0 -1 -2

이 경우 1개를 바꾸어 올바르게 되는 경우를 생각해봅시다. 

(()) -> 2번째 괄호를 바꾸는 경우

()() -> 3번째 괄호를 바꾸는 경우

이렇게 두가지가 있는 것을 알 수 있습니다.

 

규칙성을 찾아보면, depth가 음수가 나온 경우까지 등장한 오른쪽 괄호를 바꾸는 경우들이 성립하는 것을 알 수 있습니다. 이유도 생각해보면, 오류지점 이후의 괄호들은 모두 짝이 이미 맞게 배치되어 있을 것이기 때문입니다.

 

case 2. 왼쪽 괄호 ' ( ' 가 더 많은 경우

간단한 예시를 통해 살펴봅시다.

ex) (())((() depth : 1 2 1 0 1 2 3 2

위와 같은 경우를 생각해봅시다. 우선 depth가 0인 지점까지는 고칠 부분이 없다고 보아도 괜찮습니다. 

즉 (())((() 의 빨간 부분은 이미 완성되었고 수정할 부분이 없습니다. 

 

잘 생각해보면, 완성된 괄호 부분 이후에 등장하는 미완성인 괄호부분에서 오류가 발생하고, 이 부분에서 처음 여는 ' ( ' 를 제외한 ' ( ' 부분을 고칠 수 있음을 알 수 있습니다. 

(())((() 노란색으로 표시된 부분중 

(())((() 처음여는 파란 괄호를 빼고, 다음부터 오는 ' ( ' 들을 고칠 수 있습니다. 

 

이 case 1, case 2를 depth를 사용하여 구현하면 됩니다.

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <cstring>
using namespace std;

char str[100000+10];
void InputData(){
    cin >> str;
}

int solution(){
    int depth = 0;
    int left_cnt = 0;
    int right_cnt = 0;
    for(int i = 0; i<strlen(str); i++){
        if(str[i] == '('){
            left_cnt++;
            depth++;
        }
        else{
            right_cnt++;
            depth--;
        }

        if(depth < 0){ // 닫힌게 더 많다
            return right_cnt;
        }
        if(depth == 1){
            left_cnt = 0;
        }
    }
    return left_cnt;




}

int main(){
    int ans = -1;

    InputData();// 입력받는 부분

    // 여기서부터 작성
    ans = solution();

    cout << ans << endl;// 출력하는 부분
    return 0;
}