만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

면접 문제

면접 대비

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

요약
괄호와 숫자로 이루어진 문자열이 주어질 때, 각 숫자 c가 앞에서 이미 나온 문자 c개를 지워서 남은 괄호가 균형 잡힌 괄호열이 되는지 판별합니다.
난이도

보통10점 중 5점

유형
그리디, 문자열, 스택
정답자
아직 제출이 없습니다

문제

주어진 문자열 ss는 괄호("(", ")")와 숫자("0"부터 "9"까지)로 이루어져 있다. ss의 문자를 앞에서부터 차례대로 보면서 다음 연산을 수행하여 문자열 tt를 만든다.

  • "(": tt의 끝에 "("를 붙인다.
  • ")": tt의 끝에 ")"를 붙인다.
  • 0≤c≤90 \leq c \leq 9인 숫자 cc: tt에서 문자 cc개를 삭제한다. 삭제할 문자는 연속일 필요가 없다. 이 삭제가 항상 가능하다고 보장된다.

tt를 올바른 괄호 문자열로 만들 수 있는가?

입력

첫 줄에 테스트 케이스의 개수 tt (1≤t≤1041 \leq t \leq 10^{4})가 주어진다.

각 테스트 케이스에는 괄호와 숫자("()0123456789")로 이루어진 비어 있지 않은 문자열 ss가 주어진다. 문자열의 길이는 최대 3⋅1053 \cdot 10^{5}이다. 모든 문자열 길이의 합은 3⋅1053 \cdot 10^{5}를 넘지 않는다.

출력

각 테스트 케이스마다 tt를 올바른 괄호 문자열로 만들 수 있으면 "YES", 없으면 "NO"를 출력한다.

글자는 대소문자를 구분하지 않는다. 예를 들어 "yEs", "yes", "Yes", "YES"는 모두 긍정 답으로 인정된다.

예제2

  1. 예제 1

    입력
    2
((()(3)1
(()1)
    예상 출력
    Yes
No

  2. 예제 2

    입력
    5
()1()
(())
()1((((2()())))3)()
((2))()
((1()))(1)()
    예상 출력
    No
Yes
Yes
No
Yes