[백준 / python] 9012번 : 괄호

알고리즘 분류 자료구조 문자열 스택

🔗 문제 출처 https://www.acmicpc.net/problem/9012

---

📎 코드

python

T = int(input())

for tc in range(T):
  stack = []
  ip = input()
  
  for i in ip:
    if i == '(':
      stack.append(i)
    else:
      if len(stack) == 0:
        stack.append(i)
        break
      else:
        stack.pop()

  if len(stack) == 0:
    print('YES')
  else:
    print('NO')

---

괄호 문제는 대표적인 스택 자료구조 문제로, 스택에 대한 이해를 요구한다. 다른 방법으로도 풀 수 있지만 스택을 활용하여 풀어본다.

파이썬은 스택 자료구조를 제공하지 않기 때문에 리스트를 활용하여 풀어보았다.

우선 테스트케이스를 입력받고 루프를 돌린다. 리스트를 초기화해주고 괄호를 입력받는다. 입력받은 괄호들은 iterable하기 때문에 for문으로 돌려준다.

만약 입력받은 괄호가 '('라면 무조건 리스트에 넣어준다. 하지만 ')'라면 따져볼 것이 있다.

')'일 때

1. 만약 리스트가 비어있다면 어처피 VPS는 성립할 수 없기 때문에 리스트에 넣고 반복문을 탈출한다.
2. 리스트에 요소가 있다면 리스트의 마지막 원소를 pop한다.

이 반복문이 끝나고 리스트를 확인했을 때 요소가 존재한다면 VPS가 아닌 것이고, 리스트가 비어있다면 VPS로서 모든 요소가 pop된 것이다.