열린 괄호 timer 1s memory 1024MB

여는 괄호 (와 닫는 괄호 )로만 이루어진 문자열이 주어진다. 문자열은 아래 규칙을 만족해야 한다.

• 규칙: 문자열의 어떤 앞부분을 보아도 닫는 괄호 )의 개수가 여는 괄호 (의 개수보다 많으면 안 된다.

예를 들어, 문자열 ()()는 규칙을 만족하지만, 문자열 ())(는 규칙을 만족하지 않는다. 왜냐하면 ())(에서 길이가 3인 앞부분 ())는 )의 개수 2가 (의 개수 1보다 많기 때문이다.

주어진 문자열이 규칙을 만족하도록 만들기 위해, 문자열에서 바꿔야 하는 글자(를 )로 바꾸거나 그 반대 )의 최소 개수를 구하는 프로그램을 작성하라. 글자를 새로 추가하거나 제거하는 것은 허용되지 않는다.