[백준/스택] 9012. 괄호 (지긋지긋 😅😅😅)

오늘은 싸피에서 스택에 관해 배웠다

복습으로는 백준에 있는 스택 문제 풀기..

다 풀고 싶었는데 어제 풀다 만 브루투토스에 체스가 너무 오래 걸려서 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()
여러가지 숫자를 입력받거나 리스트를 씌워주거나 띄어쓰기를 하는 경우는 원래 알던 그대로 입니🦫