레이팅 미적용설명
베시(Bessie)는 방금 새 노트북을 샀지만, 작은 키보드에 비해 발굽이 너무 커서 타자를 잘 치지 못한다는 것을 깨달았다. 베시는 방금 자신이 가장 좋아하는 패턴인 균형 잡힌 괄호 문자열을 입력해 보았다. 그런데 문자 하나를 잘못 입력하여 (를 )로, 또는 그 반대로 바꿔 버렸을지도 모른다는 것을 깨달았다. 문자열에서 그 위치의 괄호 하나를 반대로 바꾸면 전체 문자열이 균형 잡히게 되는 위치의 수를 계산하는 것을 베시에게 도와주자.
괄호 문자열이 "균형 잡혔다"는 것은 (의 개수와 )의 개수가 같고, 문자열의 어떤 접두사에서도 (의 개수가 )의 개수 이상인 것을 말한다.
제약
입력 형식
첫째 줄: 길이 N (1 <= N <= 100,000)의 괄호 문자열.
출력 형식
입력 문자열에서 그 한 위치의 괄호를 반대로 바꾸면 전체 문자열이 균형 잡히게 되는 위치의 수 (없으면 0).
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
typo.in · 출력을 쓸 파일 typo.out예제 1
입력
()(())))출력
4설명
Output details: Reversing the parenthesis at position 2, 5, 6, or 7 results in a balanced string.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > November > Bronze
태그