괄호고치기 timer 1s memory 128MB

괄호로 구성된 문자열이 주어졌을 때, 가능한한 최소한의 수정을 통해서(괄호의 추가와 삭제는 할 수 없다.) 

올바른 괄호쌍을 만드는 프로그램을 작성하라.

괄호 문자는 '()', '[]', '{}' 3가지로 구성되어있다.

'(', '[', '{' 의 경우 괄호쌍을 열때 사용하며, ')', ']', '}' 의 경우 괄호쌍을 닫을 때 사용한다.

괄호 문자열은 다음의 규칙에 따라 구성되어진다.

빈 문자열도 올바른(well-formed) 괄호 문자열이다. s가 올바른 괄호 문자열이라면, (s), [s], {s} 역시 올바른 괄호 문자열이다. s와 t가 올바른 괄호 문자열이라면, 이 둘을 합친 st역시 괄호 문자열이다.(ts 역시 괄호 문자열이다.)

임의의 문자열이 입력 되었을 때 괄호문자를 바꾸어 올바른 괄호 문자열이 될 수 있는 최소 수정 횟수를 출력하시오.