[백준] 괄호_9012번

괄호_9012번

(2022년 4월 29일)

코드

def pprint(stack):
    if stack:  # not empty
        print("NO")
    else:
        print("YES")


def vps(array):
    stack = []
    while array:
        ps = array.pop(0)
        if stack:  # not empty
            if (stack[-1] == ps) or (stack[-1] == ')' and ps == '('):
                stack.append(ps)
            else:
                stack.pop(-1)
        else:
            stack.append(ps)
    pprint(stack)


n = int(input())
for _ in range(n):
    vps(list(input()))

---

풀이노트

• 2학년 1학기 자료구조에 배운 연산자 계산기 방법 활용
• stack 이용
• array 앞에서부터 pop 하고 stack에 넣어줌
• array[0](array의 첫번째 문자) == stack[-1](stack의 top) : stack.pop(-1) 함
• array[0](array의 첫번째 문자) != stack[-1](stack의 top) : stack.append(array[0]) 함
• 예외처리 : ) 이 들어있고 ( 가 들어올 차례인 경우에는 stack.pop(-1) 하면 안 됨
• stack 이 비어있으면 VPS 이므로 'YES' 를 출력하고, stack 에 값이 남아 있으면 'NO' 를 출력함

---

소요시간 : 30분

---

(2023년 1월 3일) 다시 풀어 봄

코드

# 2023-01-03 20:20:49
# https://www.acmicpc.net/problem/9012

def pprint(stack) :
    if stack == [] :
        print("YES")
    else :
        print("NO")

def vps(str) :
    stack = []
    for s in str :
        if stack == [] :
            stack.append(s)
        elif stack[-1] == '(' and s == ')' :
            stack.pop()
        else :
            stack.append(s)
    pprint(stack)

n = int(input())
for _ in range(n) :
    str = input()
    vps(str)

---

풀이노트

• stack 이용
  • stack.append(s) : stack 구조에 넣기
  • stack.pop() : 마지막 원소 빼기
• stack에 값이 빠지는 경우만 고려
  • stack의 마지막 원소가 ( 이고, 새롭게 들어갈 원소가 ) 인 경우만 존재
  • elif stack[-1] == '(' and s == ')'
• stack에 값이 추가되는 경우는 이를 제외한 나머지 경우임

---

소요시간 : 18분