๐ ์ถ์ฒ - 9012 - ๊ดํธ
๋ฌธ์ ์ค๋ช
๊ดํธ ๋ฌธ์์ด(Parenthesis String, PS)์ ๋ ๊ฐ์ ๊ดํธ ๊ธฐํธ์ธ โ(โ
์ โ)โ
๋ง์ผ๋ก ๊ตฌ์ฑ๋์ด ์๋ ๋ฌธ์์ด์ด๋ค. ๊ทธ ์ค์์ ๊ดํธ์ ๋ชจ์์ด ๋ฐ๋ฅด๊ฒ ๊ตฌ์ฑ๋ ๋ฌธ์์ด์ ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด(Valid PS, VPS)์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค. ํ ์์ ๊ดํธ ๊ธฐํธ๋ก ๋ โ( )โ
๋ฌธ์์ด์ ๊ธฐ๋ณธ VPS ์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค. ๋ง์ผ x
๊ฐ VPS ๋ผ๋ฉด ์ด๊ฒ์ ํ๋์ ๊ดํธ์ ๋ฃ์ ์๋ก์ด ๋ฌธ์์ด โ(x)โ
๋ VPS ๊ฐ ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ VPS x ์ y๋ฅผ ์ ํฉ(concatenation)์ํจ ์๋ก์ด ๋ฌธ์์ด xy๋ VPS ๊ฐ ๋๋ค. ์๋ฅผ ๋ค์ด โ(())()โ
์ โ((()))โ
๋ VPS ์ด์ง๋ง โ(()(โ
, โ(())()))โ
, ๊ทธ๋ฆฌ๊ณ โ(()โ
๋ ๋ชจ๋ VPS ๊ฐ ์๋ ๋ฌธ์์ด์ด๋ค.
์ฌ๋ฌ๋ถ์ ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง ๊ดํธ ๋ฌธ์์ด์ด VPS ์ธ์ง ์๋์ง๋ฅผ ํ๋จํด์ ๊ทธ ๊ฒฐ๊ณผ๋ฅผ YES
์ NO
๋ก ๋ํ๋ด์ด์ผ ํ๋ค.
์
๋ ฅ
์
๋ ฅ ๋ฐ์ดํฐ๋ ํ์ค ์
๋ ฅ์ ์ฌ์ฉํ๋ค. ์
๋ ฅ์ T๊ฐ์ ํ
์คํธ ๋ฐ์ดํฐ๋ก ์ฃผ์ด์ง๋ค. ์
๋ ฅ์ ์ฒซ ๋ฒ์งธ ์ค์๋ ์
๋ ฅ ๋ฐ์ดํฐ์ ์๋ฅผ ๋ํ๋ด๋ ์ ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ๋ฐ์ดํฐ์ ์ฒซ์งธ ์ค์๋ ๊ดํธ ๋ฌธ์์ด์ด ํ ์ค์ ์ฃผ์ด์ง๋ค. ํ๋์ ๊ดํธ ๋ฌธ์์ด์ ๊ธธ์ด๋ 2 ์ด์ 50 ์ดํ์ด๋ค.
์ถ๋ ฅ
์ถ๋ ฅ์ ํ์ค ์ถ๋ ฅ์ ์ฌ์ฉํ๋ค. ๋ง์ผ ์
๋ ฅ ๊ดํธ ๋ฌธ์์ด์ด ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด(VPS)์ด๋ฉด โYESโ
, ์๋๋ฉด โNOโ
๋ฅผ ํ ์ค์ ํ๋์ฉ ์ฐจ๋ก๋๋ก ์ถ๋ ฅํด์ผ ํ๋ค.
์ ์ถ๋ ฅ ์
์์ ์ ๋ ฅ | ์์ ์ถ๋ ฅ | |
---|---|---|
6 (())()) (((()())() (()())((())) ((()()(()))(((())))() ()()()()(()()())() (()((())()( | NO NO YES NO YES NO | |
3 (( )) ())(() | NO NO NO |
์ด๋ฐ ๋ฌธ์ ๋ stack
์ ์ด์ฉํด ํด๊ฒฐํ๋ฉด ๊ฐ๋จํ๋ค. ์ฒ์์ counting ํด์ ์์๊ฐ ๋๋ฉด NO
๋ฅผ ์ถ๋ ฅํ๊ณ ์ถ๊ฐ ์ต์
๋ค์ ์ง์ ํด NO
๋ฅผ ํ๋ณํ๋๋ฐ, ์ด ๋ฐฉ๋ฒ๋ณด๋ค๋ stack
์ ์ด์ฉํ๋ ๊ฒ์ด ํจ์ฌ ๋ ๊ฐ๋จํ๋ค. ๊ทธ๋ฌ๋ฉด ๊ฐ์ด ํ๋ฒ ์์๋ด๋ณด์!
Logic
1.stack
์ด ๋น์ด์๋ค๋ฉด ์๋ก์ด ๊ฐ ์ถ๊ฐ
2.'('
๋ฅผ ์ ๋ ฅ ๋ฐ๋๋ค๋ฉดstack
์ ์ถ๊ฐ
3.')'
๋ฅผ ์ ๋ ฅ ๋ฐ๋๋ค๋ฉดstack
๋ง์ง๋ง ๊ฐ์ด'('
์๋์ง ์ฒดํฌํ๊ณ ๋ง์ผ๋ฉดpop
ํ๊ธฐ
4. ์ ๋ ฅ ๋ฐ์ ๋ฌธ์ ์ ์ฒด๋ฅผ ์ฒดํนํ ํstack
์ ๊ธธ์ด๊ฐ ๋จ์์์ผ๋ฉด VPS๊ฐ ์๋ ๊ฒ์ด๊ธฐ ๋๋ฌธ์NO
๋ฐํ
def checkVPS(vps):
stack = []
for i in range(len(vps)):
if len(stack) == 0:
stack.append(vps[i])
elif vps[i] == '(':
stack.append(vps[i])
elif vps[i] == ')':
if stack[-1] == '(':
stack.pop()
else:
break
if len(stack) != 0:
print('NO')
else:
print('YES')
N = int(input())
for i in range(N):
vps = input()
checkVPS(vps)