백준 9012 괄호 - 파이썬

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

스택에서 아이디어를 뽑아낸 문제이다.

'괄호'는 스택의 단골 주제인데, 이 문제는 "(", ")" 두 종류만 신경쓰면 되는 초심자용 문제이다.

'괄호가 닫히려면 열린 적이 있어야 한다'를 명심하면 풀 수 있는 문제이다.

 

 

stack이라는 리스트를 선언해주고 스택처럼 썼다.

 

문자열을 순회하며 "("이 나타나면 stack에 넣어준다.

")"이 나타나면 stack을 살펴본다.

"("가 하나라도 존재한다면 열린 적이 있는 괄호니까 pop해주고 넘어간다. 열린 괄호를 닫았다는 정도의 의미이다.

만약 stack이 비어있다면 열리지 않은 괄호를 닫아버린 거니까 바로 틀렸다고 지적해준다.

 

순회를 마친 뒤 stack에 "("가 들어있으면 짝이 안맞는다는 소리다.

"("가 ")"보다 많았다는 의미니까 역시 올바른 괄호가 아니다.

 

for _ in range(int(input())):
    data = input()
    stack = [] # "("를 보관할 스택
    answer = "YES"

    for d in data:
        if d == "(":
            stack.append("(")
        else:
            if stack: # 괄호가 열린 적이 있으니 OK
                stack.pop()
            else: # 잘못된 괄호 NO!
                answer = "NO"
                break

    if stack: # 여는 괄호가 닫는 괄호보다 많다는 뜻 NO!
        answer = "NO"

    print(answer)

 

---

 

눈치 빠른 사람은 이미 알았겠지만 스택이 굳이 진짜 스택이지 않아도 된다.

어차피 "("만 집어넣고 있으니 구분할 필요가 없기 때문이다.

 

stack을 리스트가 아니라 정수로 선언하고, 들어 있는 "("의 개수만 세어주는 것이 더 합리적인 풀이이다.

 

from sys import stdin

for _ in range(int(input())):
    data = stdin.readline().rstrip()
    stack = 0

    for d in data:
        if d == "(":
            stack += 1
        else:
            if stack:
                stack -= 1
            else:
                stack += 1
                break

    if stack:
        print("NO")
    else:
        print("YES")