[LeetCode] 20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

---

접근 방법

• 제일 나중에 열린 괄호가 먼저 닫히는 구조이므로 stack 자료형을 사용하는 것이 알맞을 것이라 생각했다. 파이썬의 list 자료형은 append 와 pop 을 사용하여 stack 처럼 사용이 가능하므로 list 자료형을 사용하기로 하였다.

class Solution:
  def isValid(self, s: str) -> bool:
      stack = []
      brakets = {'(':')', '{':'}', '[':']'}
      for char in s:
          if char in brakets.keys():
              stack.append(brakets[char])
          elif char in brakets.values() and (not stack or stack.pop() != char):
              return False
      return not stack

• 브라켓 딕셔너리를 만들어 키에 여는 괄호, 밸류에 닫는 괄호를 넣어 사용하였다.

• 참고할만한 코드들을 찾아보던 중, 마지막 리턴값을 적을 때, not stack 과 같은 방식을 사용하면 짧게 정리가 되는 것을 배울 수 있었다.

	# 동일한 코드
	return True if not stack else False
    return len(stack) == 0
    return not stack

---

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

• 백준 9012번 문제도 동일하게 풀 수 있다.

  괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
  
  여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

import sys

def check_vps(str):
    stack = []
    for c in str:
        if c == '(':
            stack.append(c)
        elif c == ')' and stack:
            stack.pop()
        elif c == ')' and not stack:
            return False
    return not stack

t = int(sys.stdin.readline().strip())
for _ in range(t):
    print('YES') if check_vps(sys.stdin.readline().strip()) else print('NO')