Bessie는 새 노트북에 균형 잡힌 괄호 문자열을 입력하려 하지만 큰 발굽 때문에 서툴러 계속 오타를 냅니다. 균형을 잡으려면 몇 문자를 뒤집어야 하는지(여는 괄호를 닫는 괄호로 또는 반대로 바꿈) 최솟값을 구하세요.
균형의 정의는 여러 가지입니다. 가장 간단한 것은 여는 괄호와 닫는 괄호의 전체 개수가 같고, 모든 접두사에서 여는 괄호가 닫는 괄호 이상으로 많은 것입니다. 다음 문자열들은 균형 잡혀 있습니다.
() (()) ()(()())
다음은 그렇지 않습니다.
)( ())( ((())))
입력
- 1번 줄: 길이가 짝수이며 최대 100,000자인 괄호 문자열 $A$.
출력
- 1번 줄: 균형 잡힌 문자열로 만들기 위해 뒤집을 괄호 수의 최솟값인 정수 하나.
예제
입력 1
())(
출력 1
2
참고
마지막 괄호와 가운데 두 닫는 괄호 중 하나를 뒤집어야 합니다.
문제 작성: Brian Dean, 2012