파일 업로드

균형잡힌 괄호

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

수연은 펜으로 균형 잡힌 괄호 문자열 쌍을 적으려고 하지만, 그녀의 손이 문자를 계속 잘못 적고 있습니다.  그녀를 도와서 문자열이 균형 잡히도록 최소 몇 개의 괄호를 뒤집어야 하는지 계산해주세요. (예 : 좌괄호를 우괄호로 바꾸거나 반대로)

"균형 잡힌" 괄호 문자열을 정의하는 여러 가지 방법이 있을 수 있습니다. 아마 가장 간단한 정의는 전체적으로 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 하며, 문자열의 어떤 접두사에 대해서도 왼쪽 괄호의 개수가 오른쪽 괄호의 개수와 최소 같아야 한다는 것입니다. 

예를 들어 다음 문자열은 모두 균형 잡힌 문자열입니다:

  • ()
  • (())
  • ()(()())

반면, 다음 문자열들은 균형을 이루지 못합니다:

  • )(
  • ())(
  • ((())))
💻 입력
  • 1번째 줄: 괄호의 문자열로, 최대 100,000까지의 짝수 길이를 가집니다.
🖨️ 출력
  • 1번째 줄: 문자열을 균형잡힌 문자열로 바꾸기 위해 전환해야 하는 괄호의 최소 개수를 나타내는 정수를 출력합니다.

💻 예제 입력 1
())(
🖨️ 예제 출력 1
2

출처: USACO 2012 November Contest, Silver Problem 1. Clumsy Cows