[백준]9012_괄호(자료구조/python)

괄호  

시간 제한/메모리 제한/제출/정답/맞힌 사람/정답 비율

1 초

128 MB

181847

85035

61208

45.696%

문제

괄호 문자열(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

---

풀이 코드

N = int(input())
for _ in range(N):
    stack = []
    x_list = input()
    for x in x_list:
        if x == '(':    #여는 괄호는 stack에 쌓는다.
            stack.append(x)
        elif x == ')':
            if stack:       
                stack.pop()
            else:
                print("NO") #stack이 비어있다면 여는 괄호가 없는 상태에서 닫는 괄호가 있는 것이기 때문에 "NO" 이다
                break
    else : #for else 문 for문에서 break 기록이 없다면 else 실행.
        if not stack:
            print("YES")
        else :
            print("NO")

 

처음에 너무 쉽잖아? 라고 생각하고 여는괄호"(" = +1 ) , 닫는괄호")" = -1 해가면서 풀었는데 당연히 false...

그렇게 여는괄호와 닫는괄호의 개수만 생각하는 바보였음..

 

이 문제는 여는괄호와 닫는괄호가 숫자는 같더라도, 중간에 어긋나면 NO 를 줘야하는 문제임.

 

문제 해결 방색으로는 stack 을 사용해서 여는 괄호일 경우 쌓고 닫는 괄호일 경우 제거한다!

그 과정에서 stack이 비어있는데 닫는 괄호가 나왔다면 열지 않은 괄호를 닫은 것이기 때문에 NO 를 주면 된다.

NO 가 나오지 않고 문자열 점검을 모두 끝냈다면, stack이 비어있는지를 확인해, 열어둔 괄호가 모두 닫혔는지 검증하면 끝이난다.

 

stack을 공부할 때 너무 유명한 문제라고 하니 잘 외워두자!

 

<Reference>

https://wookcode.tistory.com/49

[백준] 9012번 괄호 (Python)