[알고리즘] Leetcode-valid-parentheses 파이썬 문제 풀이

문제 링크

문제

Stack을 사용하는 가장 기본적인 유형이라고 보면 된다. 괄호가 나열되어 있는 문자열을 입력받아서 성립이 되는 것인지 묻는 유형이다.

입출력 예시

괄호가 열린 순서대로 괄호가 닫히면 true, 아니라면 false가 반환되면 된다.

조건

문자열의 길이는 1보다 크며, 10의 4승보다는 작다 => O(n^2)으로 풀면 간당간당 하기 때문에 시간복잡도가 더 낮은 풀이방법을 생각해야 한다.

풀이

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

스택을 선언하고, 문자열을 for문으로 돌리면서 괄호를 하나씩 받아온다. 만약 받아온 괄호가 여는 괄호이면 해당 괄호에 매칭되는 닫는 괄호를 스택에 넣어주는 방법을 사용했다.
만약 닫는 괄호가 왔는데 stack이 비어있거나 stack.pop()한 괄호가 해당 괄호랑 다르다면 전체 괄호가 성립하지 않기 때문에 False를 반환해준다.
만약 for문이 끝난 후에도 stack에 괄호가 남아있다면 열린 괄호만큼 닫힌 괄호가 오지 않은 것이기 때문에 not stack으로 해서 stack이 비어있다면 True, stack에 하나라도 남아있다면 False를 반환하게 했다.