์ค๋์ ์ธํผ์์ ์คํ์ ๊ดํด ๋ฐฐ์ ๋ค
๋ณต์ต์ผ๋ก๋ ๋ฐฑ์ค์ ์๋ ์คํ ๋ฌธ์ ํ๊ธฐ..
๋ค ํ๊ณ ์ถ์๋๋ฐ ์ด์ ํ๋ค ๋ง ๋ธ๋ฃจํฌํ ์ค์ ์ฒด์ค๊ฐ ๋๋ฌด ์ค๋ ๊ฑธ๋ ค์ 2๋ฌธ์ ๋จ์๋ค...
๋ด์ผ ํด์ผ์ง;;;;; ๋ค์์ ์ฒด์ค๋ ์๊ฐ๋๋ฉด ์ ์ด๋ณด๋๊ฑธ๋ก
์๋ก ์ด ๋๋ฌด ๊ธธ์๊ณ ์ค๋ ์๊ฐํด ๋๋ฆด ๋ฌธ์ ๋ ๋ฐฑ์ค 9012. ๊ดํธ์ ๋๋ค!!!
์ค๋ swea์์๋ ๋น์ทํ ๋ฌธ์ ๋ฅผ ํ์๋๋ฐ ์กฐ๊ธ ์ฌ์ด ๋ฒ์ ์ ๋๋ค ^^
๊ทธ๋ผ ๊ณ ๐๐
๋ฌธ์
๊ดํธ ๋ฌธ์์ด(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โ๋ฅผ ํ ์ค์ ํ๋์ฉ ์ฐจ๋ก๋๋ก ์ถ๋ ฅํด์ผ ํ๋ค.
์์ ์ ๋ ฅ 1 ๋ณต์ฌ
6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(
์์ ์ถ๋ ฅ 1 ๋ณต์ฌ
NO
NO
YES
NO
YES
NO
์ด ๊ดํธ ๋ฌธ์ ๊ฐ ์ฝ๊ฐ ์คํ์ ๊ธฐ๋ณธ๋ฌธ์ ๋๋?? ๋จผ๊ฐ ์ํ์ ์กฐ๊ธ ์์ฉํด์ ๋์ฌ๊ฑฐ ๊ฐ์ ๋๋์ด ๋๋๋ฐ์...
๋จผ์ ์ ๊ฐ ์ง ์ฝ๋ ์๊ฐํด ๋๋ฆฌ๊ฒ ์ต๋๋ค!!!
# 9012. ๊ดํธ - ์ค๋ ๋๋ฅผ ์ง๊ฒน๊ฒ ํ ^^ : ์ค๋ ํ๊ต์์ ์ด๊ฑฐ ๋น์ทํ ๋ฌธ์ ํ 2์๊ฐ ๋จธ๋ฆฌ ์ธ๋งธ๊ฑฐ๋ฉ์...
stack = [] # ๊ดํธ๋ฅผ ๋ด์ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค์ด ์คฌ์ต๋๋ค
def gal(text): # ํจ์๋ก ๋ง๋๋๊ฒ ์กฐ๊ธ ํธํด์ ธ์ ๋ง๋ค์์ต๋๋ค
for ch in text: # ํ
์คํธ ๋ด๋ถ๋ฅผ ์ํํ๋ฉด์
if ch == '(': # ๋ฌธ์'('๊ฐ ์์ผ๋ฉด
stack.append(ch) # ๋ฌธ์๋ฅผ ๋ฆฌ์คํธ์ ์ถ๊ฐํด์ค๋๋ค
elif ch == ')': # ๋ฌธ์')'๊ฐ ์์ผ๋ฉด
if len(stack) == 0: # ๋ฆฌ์คํธ์ ๊ธธ์ด๋ฅผ ํ์ธํด์ค์ผ ํ๋๋ฐ 0์ด๋ผ๋ฉด ์ด๋ฆฐ๊ธฐํธ๊ฐ ์์ด์ ํ๋ฆฐ text์
๋๋น
return 'NO' # ๊ณ ๋ก NO๋ฅผ ๋ฐํํด ์คฌ์ด์
else: # ๊ธธ์ด๊ฐ 0์ด ์๋๋ผ๋ฉด...
if stack[-1] == '(': # ์คํ์ ๋ง์ง๋ง์ (๊ฐ ์์ผ๋ฉด
stack.pop() # ๋ง์ง๋ง (๋ฅผ ์ญ์ ํ๊ณ
continue # ๊ณ์ํด์ ๋ค์ ๋ฌธ์๋ฅผ ํ์ธํด ์คฌ์ต๋๋ค
else:
return 'NO' # ํ์ง๋ง ์ด๋ฆฐ๊ธฐํธ '('๊ฐ ์๋ ๋ค๋ฅธ๊ฒ ๋ค์ด์์ผ๋ฉด ํ๋ฆฐ ๋ฌธ์ฅ์ด๊ฒ ์ฃ
if len(stack) == 0: # ๊ฒฐ๋ก ์ ์ผ๋ก ')'๊ฐ ๋์ฌ๋ '('์ ์ง์ ์ผ๋ฏ๋ก ์์ด ๋ง๋๋ค๋ฉด
#์คํ์ ๋จ์์๋๊ฒ ์์ด์ผ ํ๋๊น
return 'YES' # YES๋ฅผ ๋ฐํํฉ๋๋ค
else:
return 'NO' # ์๋๋ฉด 'NO'
import sys # ์คํ ๋ฌธ์ ๋ฅผ ํ๊ณ ์ฒ์์ผ๋ก ์๊ฐ์ด๊ณผ๊ฐ ๋ ์ ์์์์ต๋๋ค..
T = int(sys.stdin.readline())
for _ in range(T):
bracket = sys.stdin.readline()
stack = [] ########์ฌ์ค ์ ์์ ํจ์๊ฐ ์๋๋ผ ์ด๋ถ๋ถ์ด ํ๋ ธ๋๋ฐ์....
#์คํ์ ํ ๋๋ง๋ค ์ด๊ธฐํํด์ค์ผํด์.... ํ๋ฆฐ ๊ฐ์ด ๋ค์ด์๋ค๋ฉด ๋ค์ ์ฌ๋ก๋ ํ๋ฆฌ๊ฑฐ๋ฑ์..... ๊ธฐ์ด์ ์ธ ๋ถ๋ถ์ด๋๊น ๊ผญ ๊ธฐ์ตํ๊ธฐ!!!!
result = gal(bracket)
print(result)
์ ๊ฐ ๋๋ฌด ์ค๋ช ์ ์ฅํฉํ๊ฒ ์ ์๋๋ฐ ๊ฐ๋จํ๊ฒ ์์ฝํ์๋ฉด...
์ฑ๋ฆฝ โ
1. () ์์ด ๋ง์์ผํจ : '(', ')'์ ๊ฐ๊ฐ์ ๊ฐ์๊ฐ ๊ฐ์์ผ ํจ (=๋ฆฌ์คํธ์ ๊ธฐํธ๊ฐ ๋จ์์์ผ๋ฉด ์๋จ)
2. ๋ซํ ๊ธฐํธ')'๊ฐ ๋จผ์ ๋์ค๋ฉด ์๋๋ค
์์ ํจ์ ๊ตฌํํ๋๋ฐ๋ ์ค๋ ๊ฑธ๋ ธ์ง๋ง...
ํ๋ ์ผ์ด์ค ์คํจํ๊ฒ ํ ๋ถ๋ถ์ ๋ฆฌ์คํธ ์ด๊ธฐํ์์ต๋๋ค...
์๋ชป๋ ์ผ์ด์ค๋ฅผ ํํ์ ๋จ์์๋ ๋ฆฌ์คํธ๋ฅผ ์ด๊ธฐํ ํด์ผํ๋๋ฐ ๋ฐ๋ก ์ด๊ธฐํํ๋ ๋ถ๋ถ์ ์ ๋ฃ์ด์คฌ๋๋ผ๊ตฌ์..
์ ๋ง ๊ธฐ๋ณธ์ ์ด์ง๋ง ์ ๋ฃ์ด์ผ๋ฉด ํ๋ฆฌ๋ ์ค์ํ ๋ถ๋ถ์ด๋๊น ํ๋ฒ ๋ ์๊ฐํด๋ณด์๊ตฌ์ฌ ^___________^
๊ทธ๋ฆฌ๊ณ ์คํ๋ฌธ์ ๋ก ๋์ด์ค๋ฉด์ ์ฒ์์ผ๋ก ํ์ด์ฌ์์ ์๊ฐ์ด๊ณผ๊ฐ ๋ฌ๋๋ฐ์ฌ...
๋น ๋ฅธ ์ ๋ ฅ์ผ ๋ฐ๊ฟ์ฃผ๋ฉด ์๊ฐ์ด๊ณผ ์๋ฌ๋ ์๋ฉ๋๋ค!!!
๋น ๋ฅธ ์ ์ถ๋ ฅ
import sys
num = int(sys.stdin.readline()) => input()
์ฌ๋ฌ๊ฐ์ง ์ซ์๋ฅผ ์ ๋ ฅ๋ฐ๊ฑฐ๋ ๋ฆฌ์คํธ๋ฅผ ์์์ฃผ๊ฑฐ๋ ๋์ด์ฐ๊ธฐ๋ฅผ ํ๋ ๊ฒฝ์ฐ๋ ์๋ ์๋ ๊ทธ๋๋ก ์ ๋๐ฆซ
'algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋ฐฑ์ค 1920. ์์ฐพ๊ธฐ (set(), Binary Search) (0) | 2023.08.15 |
---|---|
swea 4875. ๋ฏธ๋ก(dfs & ๋ธํ ํ์) (0) | 2023.08.15 |
[๋ฐฑ์ค - ๋ธ๋ฃจํธ ํฌ์ค]19532. ์ํ์ ๋น๋๋ฉด๊ฐ์์ ๋๋ค (2) | 2023.08.09 |
๋ฐฑ์ค ์ฌํ 10988 ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ์ธํ๊ธฐ (2) | 2023.07.28 |
[๋ฐฑ์ค] ๋ฐ๋ณต๋ฌธ๐ตโ๐ซ 10952๋ฒ A+B - 5 (2) | 2023.07.20 |