와일드카드 괄호 문자열

시간 제한1초메모리 제한1024 MB

요약

'(', ')', '?', '*'로 이루어진 문자열에서 '?'는 괄호 하나로, '*'는 임의 길이의 괄호 문자열로 바꿔 전체를 올바른 괄호 문자열로 만들 수 있는지 판정한다.

난이도: 보통10점 중 7점
유형: 그리디, 문자열, 동적 계획법, 구현
정답자: 아직 제출이 없습니다

문제

‘(’, ‘)’로 이루어진 문자열이 올바른 괄호 문자열이라는 것은 다음을 의미합니다.

$S$ 가 빈 문자열이면, $S$ 는 올바른 괄호 문자열입니다.
$S$ 가 올바른 괄호 문자열이면, $S$ 의 앞뒤에 각각 ‘(’와 ‘)’를 붙여 만든 문자열 “( $S$ )” 는 올바른 괄호 문자열입니다.
$S$ 와 $T$ 가 올바른 괄호 문자열이면, $S$ 와 $T$ 를 붙여 만든 문자열 “ $ST$ ”는 올바른 괄호 문자열입니다.
위 세 규칙을 통해 만들 수 없는 문자열은 올바른 괄호 문자열이 아닙니다.

예를 들어, “(())()”, “()()”은 올바른 괄호 문자열이고 “)(”, “())(”는 올바른 괄호문자열이 아닙니다.

문자열 $S$ 가 주어집니다. $S$ 는 ‘(’, ‘)’, ‘?’, ‘*’로 이루어진 문자열입니다. ‘?’ 문자를 ‘(’이나 ‘)’로, ‘*’ 문자를 ‘(’와 ‘)’로 이루어진 길이가 $0$ 이상인 원하는 문자열로 대체하여 $S$ 를 올바른 괄호 문자열로 만들 수 있나요?

입력

첫 줄에 테스트케이스의 수 $T$ 가 주어집니다. $(1 \le T \le 10\\,000)$

각 테스트케이스의 첫 줄에는 ‘(’, ‘)’, ‘?’, ‘*’로 이루어진 길이가 $1$ 이상 $500\\,000$ 이하인 문자열 $S$ 가 주어집니다.

입력에서 주어진 문자열 $S$ 의 길이 합은 $500\\,000$ 을 넘지 않습니다.

출력

각 테스트케이스마다 한 줄에 하나씩, ‘?’ 문자를 ‘(’이나 ‘)’로, ‘*’ 문자를 ‘(’, ‘)’로 이루어진 길이가 $0$ 이상인 원하는 문자열로 대체하여 $S$ 를 올바른 괄호 문자열로 만들 수 있다면 “YES”, 불가능하면 “NO”를 출력하세요.

예제1

예제 1

입력

4
()??))
())*(())
*)))(((*
?()(?*))(()?

예상 출력

YES
NO
YES
YES