6033 : 괄호 최소 제거
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
소문자 알파벳과 소괄호
이 문자열을 올바른 괄호 균형을 가진 문자열로 만들기 위해 제거해야 하는 최소 괄호의 개수를 구하는 프로그램을 작성하십시오.
예를 들어
[제약 조건]
• 테스트케이스 수 $T$: $1 \le T \le 100$ (정수)
• 각 문자열 길이: $1 \le$ 길이 $\le 1{,}000$
• 문자열은 소문자와 소괄호로만 구성됩니다.
(, )가 혼합된 문자열이 주어집니다.이 문자열을 올바른 괄호 균형을 가진 문자열로 만들기 위해 제거해야 하는 최소 괄호의 개수를 구하는 프로그램을 작성하십시오.
예를 들어
a(b(c)에서는 맨 앞의 ( 혹은 중간의 ( 중 하나를 제거해야 유효하게 되므로 최소 제거 개수는 1개입니다.[제약 조건]
• 테스트케이스 수 $T$: $1 \le T \le 100$ (정수)
• 각 문자열 길이: $1 \le$ 길이 $\le 1{,}000$
• 문자열은 소문자와 소괄호로만 구성됩니다.
입력 설명
첫째 줄에 테스트케이스 수 $T$가 주어집니다. ($1 \le T \le 100$)
둘째 줄부터 $T$개의 줄에 소문자와 소괄호가 섞인 문자열이 주어집니다. (길이 $\le 1,000$)
둘째 줄부터 $T$개의 줄에 소문자와 소괄호가 섞인 문자열이 주어집니다. (길이 $\le 1,000$)
출력 설명
각 테스트케이스마다 올바른 괄호 문자열을 만들기 위해 제거해야 하는 최소 괄호 개수를 줄바꿈하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
a(b(c)
((a)
a)b)
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
2
2도움
스택에 매칭되지 않은 `(`의 인덱스를 저장합니다. `)`를 만났을 때 스택이 비어 있다면 매칭에 실패한 `)`로 판단해 제거 개수를 증가시키고, 스택에 값이 있다면 pop합니다. 최종 제거 수는 (남아있는 `(`의 수 + 매칭 실패한 `)`의 수)입니다.