728x90
๋ฐ˜์‘ํ˜•

์˜ค๋Š˜์€ ์‹ธํ”ผ์—์„œ ์Šคํƒ์— ๊ด€ํ•ด ๋ฐฐ์› ๋‹ค

๋ณต์Šต์œผ๋กœ๋Š” ๋ฐฑ์ค€์— ์žˆ๋Š” ์Šคํƒ ๋ฌธ์ œ ํ’€๊ธฐ..

๋‹ค ํ’€๊ณ  ์‹ถ์—ˆ๋Š”๋ฐ ์–ด์ œ ํ’€๋‹ค ๋งŒ ๋ธŒ๋ฃจํˆฌํ† ์Šค์— ์ฒด์Šค๊ฐ€ ๋„ˆ๋ฌด ์˜ค๋ž˜ ๊ฑธ๋ ค์„œ 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()
์—ฌ๋Ÿฌ๊ฐ€์ง€ ์ˆซ์ž๋ฅผ ์ž…๋ ฅ๋ฐ›๊ฑฐ๋‚˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์”Œ์›Œ์ฃผ๊ฑฐ๋‚˜ ๋„์–ด์“ฐ๊ธฐ๋ฅผ ํ•˜๋Š” ๊ฒฝ์šฐ๋Š” ์›๋ž˜ ์•Œ๋˜ ๊ทธ๋Œ€๋กœ ์ž…๋‹ˆ๐Ÿฆซ

 

728x90
๋ฐ˜์‘ํ˜•

+ Recent posts